• UGM
  • IT Center
  • Bahasa Indonesia
    • English
    • Bahasa Indonesia
Universitas Gadjah Mada Universitas Gadjah Mada
Menara Ilmu Matematika Diskrit
  • BERANDA
  • TENTANG
    • OVERVIEW WEBSITE
    • TIM PENGEMBANG
  • Materi
    • LOGIKA MATEMATIKA
    • PEMBUKTIAN MATEMATIKA
    • HIMPUNAN
    • RELASI
    • FUNGSI DISKRIT NUMERIK
    • INDUKSI MATEMATIKA
    • PRINSIP INKLUSI DAN EKSKLUSI
    • PERMUTASI DAN KOMBINASI
    • TEOREMA BINOMIAL
    • PRINSIP SARANG MERPATI
    • ALGORITMA
    • FUNGSI PEMBANGKIT
    • RELASI REKURENSI
    • BILANGAN FIBONACCI
    • POSET
    • LATIS
    • ALJABAR BOOLE
    • PERSAMAAN DIOPHANTINE
    • RING DAN LAPANGAN
    • LAPANGAN GALOIS
    • GEOMETRI BIDANG HINGGA
    • PERSEGI LATIN
    • BALANCED INCOMPLETE BLOCK DESIGN
    • STEINER TRIPLE SYSTEM
    • TEORI BILANGAN DASAR
    • TEORI GRAF
    • POHON
  • Tutorial
    • Rekaman Latihan Soal
    • Tutorial Logika Matematika
    • Tutorial Pembuktian Matematika
    • Tutorial Himpunan
    • Tutorial Relasi
    • Tutorial Fungsi Diskrit Numerik
    • Tutorial Induksi Matematika
    • Tutorial Prinsip Inklusi dan Eksklusi
    • Tutorial Permutasi dan Kombinasi
    • Tutorial Teorema Binomial
    • Tutorial Prinsip Sarang Merpati
    • Tutorial Algoritma
    • Tutorial Fungsi Pembangkit
    • Tutorial Relasi Rekurensi
    • Tutorial Bilangan Fibonacci
    • Tutorial Poset
    • Tutorial Latis
    • Tutorial Aljabar Boole
    • Tutorial Persamaan Diophantine
    • Tutorial Ring dan Lapangan
    • Tutorial Lapangan Galois
    • Tutorial Geometri Bidang Hingga
    • Tutorial Persegi Latin
    • Tutorial Balanced Incomplete Block Design
    • Tutorial Steiner Triple System
    • Tutorial Teori Bilangan Dasar
    • Tutorial Teori Graf
    • Tutorial Pohon
  • PENELITIAN TERKAIT
    • TEORI PARTISI
    • TEORI GRAF
    • KRIPTOGRAFI
    • TEORI KODING
    • ALJABAR LINEAR
  • KONTAK KAMI
  • Beranda
  • Tutorial
  • Pembahasan Soal 1 Barisan Fibonacci

Pembahasan Soal 1 Barisan Fibonacci

  • Tutorial
  • 29 Oktober 2021, 15.39
  • Oleh: isnainiuha
  • 0

Soal Diberikan barisan Fibonacci (F_{n}) dengan F_{0}=0 dan F_{1}=1

  1. Buktikan bahwa untuk F_{n} merupakan bilangan kelipatan 5 jika dan hanya jika n merupakan bilangan kelipatan 5.
  2. Dinotasikan \phi sebagai “\emph{golden ratio}” \displaystyle \frac{\sqrt{5}+1}{2}. Buktikan bahwa

        \[\phi^{n-2}\leq F_{n}\leq \phi^{n-1}\]

    untuk setiap n\geq 2.

Pembahasan

  1. Diperhatikan bahwa

        \begin{equation*} \begin{split} F_{n}&=F_{n-1}+F_{n-2}\\ F_{n}&=(F_{n-2}+F_{n-3})+F_{n-2}\\ F_{n}&=2F_{n-2}+F_{n-3}\\ F_{n}&=2(F_{n-3}+F_{n-4})+F_{n-3}\\ F_{n}&=3F_{n-3}+2F_{n-4}\\ F_{n}&=3(F_{n-4}+F_{n-5})+2F_{n-4}\\ F_{n}&=5F_{n-4}+3F_{n-5} \end{split} \end{equation*}

    Selanjutnya, berdasarkan algoritma pembagian, misalkan n=5m+r dengan m,r\in \Z_{0} dan 0\leq r\leq 4. Dengan demikian diperoleh

        \begin{equation*} \begin{split} F_{n}&\equiv 5F_{n-4}+3F_{n-5} ~(\text{mod}~5)\\ F_{n}&\equiv 3F_{n-5} ~(\text{mod}~5)\\ F_{n}&\equiv F_{n-5} ~(\text{mod}~5)~\hspace*{4cm}~\text{karena}~\text{GCD}(3,5)=1\\ F_{n}&\equiv 3F_{n-10}~(\text{mod}~5)~\hspace*{4cm}~\text{karena}~F_{n-5}\equiv 3F_{n-10}~\text{mod}~5\\ F_{n}&\equiv F_{n-10} ~(\text{mod}~5)~\hspace*{4cm}~\text{karena}~\text{GCD}(3,5)=1\\ \vdots ~~&~~\vdots~~~~~~~~~~ \vdots\\ F_{n}&\equiv F_{n-5m} ~(\text{mod}~5)\\ F_{n}&\equiv F_{r} ~(\text{mod}~5) \end{split} \end{equation*}

    Dengan demikian diperoleh
    F_{n} merupakan bilangan kelipatan 5 jika dan hanya jika F_{r} merupakan bilangan kelipatan 5.
    Mengingat 0\leq r\leq 4 dan F_{0}=0, F_{1}=1, F_{2}=1, F_{3}=2, F_{4}=3, maka diperoleh
    F_{n} merupakan bilangan kelipatan 5 jika dan hanya jika r=0, atau dengan kata lain terbukti bahwa F_{n} merupakan bilangan kelipatan 5 jika dan hanya jika n merupakan bilangan kelipatan 5.

  2. Akan dibuktikan dengan induksi matematika bahwa untuk setiap n\geq 2 berlaku

        \[\phi^{n-2}\leq F_{n}\leq \phi^{n-1}\]

    \begin{itemize}
    \item {\bf Pangkal Induksi}: Untuk n=2 berlaku

        \begin{equation*} \begin{split} 1&\leq 1\leq \phi\\ \phi^{0} &\leq F_{2}\leq \phi^{1}. \end{split} \end{equation*}

  3. Asumsi Induksi: Diasumsikan untuk setiap bilangan asli k dengan 2\leq k\leq n berlaku

        \[\phi^{k-2}\leq F_{k}\leq \phi^{k-1}.\]

    Dengan demikian diperoleh

        \begin{equation*} \begin{split} \phi^{k-2}&\leq F_{k}\leq \phi^{k-1}\\ \phi^{k-3}&\leq F_{k-1}\leq \phi^{k-2}. \end{split} \end{equation*}

    \item Selanjutnya, akan dibuktikan untuk n=k+1 memenuhi

        \[\phi^{(k+1)-2}\leq F_{k+1}\leq \phi^{(k+1)-1}.\]

    \\
    Berdasarkan asumsi induksi, diperoleh

        \begin{equation*} \begin{split} \phi^{k-2}&\leq F_{k}\leq \phi^{k-1}\\ \phi^{k-3}&\leq F_{k-1}\leq \phi^{k-2}. \end{split} \end{equation*}

    Dengan demikian diperoleh

        \begin{equation*} \begin{split} \phi^{k-2}+\phi^{k-3}\leq &F_{k}+F_{k-1}\leq \phi^{k-1}+\phi^{k-2}\\ \phi^{k-3}(\phi+1)\leq & F_{k+1}\leq \phi^{k-2}(\phi+1)\\ \phi^{k-3}\phi^{2}\leq &F_{k+1}\leq \phi^{k-3}\phi^{2}~\hspace*{3cm}~\text{karena}~\phi+1=\phi^{2}\\ \phi^{k-1}\leq &F_{k+1}\leq \phi^{k}\\ \phi^{(k+1)-2}\leq &F_{k+1}\leq \phi^{(k+1)-1} \end{split} \end{equation*}

    Terbukti bahwa untuk n=k+1 memenuhi

        \[\phi^{(k+1)-2}\leq F_{k+1}\leq \phi^{(k+1)-1}.\]

Berdasarkan prinsip induksi matematika, diperoleh bahwa untuk setiap n\geq 0 berlaku

    \[\phi^{n-2}\leq F_{n}\leq \phi^{n-1}.\]

 

Credit: Iwan Ernanto

 

Video Penjelasan:

Leave A Comment Batalkan balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

*

Artikel Terbaru

  • Pembahasan Soal 4 Lapangan Galois
  • Pembahasan Soal 5 Lapangan Galois
  • Pembahasan Soal 3 Lapangan Galois
  • Pembahasan Soal 2 Lapangan Galois
  • Pembahasan Soal 1 Lapangan Galois

Komentar

  • jiii pada Pembahasan Soal 1 Prinsip Inklusi-Eksklusi
  • jiii pada Pembahasan Soal 1 Prinsip Inklusi-Eksklusi
Universitas Gadjah Mada

Kanal Pengetahuan dan Menara Ilmu

Fakultas Matematika dan Ilmu Pengetahuan Alam

Universitas Gadjah Mada

Sekip Utara BLS 21 Yogyakarta

© Universitas Gadjah Mada

KEBIJAKAN PRIVASI/PRIVACY POLICY

[EN] We use cookies to help our viewer get the best experience on our website. -- [ID] Kami menggunakan cookie untuk membantu pengunjung kami mendapatkan pengalaman terbaik di situs web kami.I Agree / Saya Setuju