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?
Best Answer
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}) $$