Pembahasan Soal 1 Barisan Fibonacci

[latexpage]

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:

[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]