Pembahasan Soal 1 Barisan Fibonacci

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

Alamat email Anda tidak akan dipublikasikan.

*