Prove that for the Fibonacci sequence $(F_n)$, $F_n$ divides $F_{2n}$.

Question

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?

Answer 1

Using $F_{m+n} = F_{n-1}F_m+F_nF_{m+1}$ with $m=n$, we have $$F_{2n} = F_{n-1}F_n+F_nF_{n+1} = F_n\left(F_{n-1}+F_{n+1}\right)$$

So $F_n$ divides $F_{2n}$.

Answer 2

Hint: Try to prove $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ using induction. You might need these intermediate steps:

1. $\gcd(F_n, F_{n+1}) = 1.$
2. $F_{m+n}=F_mF_{n+1}+F_{m−1}F_n.$

Answer 3

$n$th term of the Fibonacci sequence is given by$\sqrt{5}F_n=\varphi^n-(-\varphi)^{-n},$ where $\varphi=\dfrac{1+\sqrt 5}{2}.$ Now write $F_{2n}$ and factor it as a difference of two squares to reach the desire result.

Even though my proof goes without induction, if you really need, you can use induction to derive the Binet's formula.

Answer 4

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}) $$