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?
 A: 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})
$$
A: 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.$

A: $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.
A: 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}$.
