Prove that for the Fibonacci sequence $(F_n)$, $F_n$ divides $F_{2n}$.
I have a seemingly simple question to solve by induction. The question says $F_n$ divides $F_{2n}$ in the Fibonacci sequence. My thoughts on this.
First,since the n-th term of the Fibonacci sequence is given as the sum of the two previous terms, simple induction won't suffice. So I should try composite induction.
That is, supposing that $F_k$ divides $F_{2k}$ for all $k<n$, I must prove $F_{n}$ divides $F_{2n}$. Is this approach valid?
Doesn't seem to work. If I write $F_{2n}=F_{2n-1}+F_{2n-2}$ then by the inductive hypothesis, $F_{n-1}$ divides $F_{2n-2}$ but this does not help me assert that $F_n$ divides $F_{2n}$. Am I doing this wrong?
My favorite Fibonacci technique is the matrix formulation, which is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$
Then $$ \begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{2n} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ Now look at the $(1,2)$ entries and get: $$ F_{2n} = F_n(F_{n+1}+F_{n-1}) $$
Hint: Try to prove $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ using induction. You might need these intermediate steps:
- $\gcd(F_n, F_{n+1}) = 1.$
- $F_{m+n}=F_mF_{n+1}+F_{m−1}F_n.$