# Question regarding the Fibonacci sequence

Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?

• More generally, $F_{\gcd(m,n)}=\gcd(F_m,F_n)$. – lhf Sep 24 '14 at 11:29
• – lab bhattacharjee Sep 24 '14 at 11:39

Yes, induction works. Let us prove the following by induction on $q$.
If $n=qm$, then $F_n$ is divisible by F_m$$\ \ \ (1). For q = 1, (1) holds trivially. Assume that for q=k (1) holds. So, there exists an integer d such that F_{km}=dF_m. Then, we have$$\begin{align}F_{m+km}&\color{red}{=}F_{km}\times F_{m+1}+F_{km-1}\times F_m\\&=d\times F_m\times F_{m+1}+F_{km-1}\times F_m\\&=F_m\left(dF_{m+1}+F_{km-1}\right).\end{align}$$So, F_{m+km} is divisible by F_m. Hence, (1) holds for any positive integer q. Q.E.D. P.S. Note that the red equality (\color{red}{=}) comes from the following :$$F_{n+m}=F_m \times F_{n+1}+F_{m-1}\times F_n\tag 2$$This can be proven by induction on n. For n=1,2, (2) holds. Assume that (2) holds for n=k,k+1. Then, we have$$\begin{align} F_m\times F_{k+3}+F_{m-1}\times F_{k+2}& =F_m \times \left(F_{k+2}+F_{k+1}\right)+F_{m-1}\times\left(F_{k+1}+F_k\right)\\& =F_m \times F_{k+2}+F_m \times F_{k+1}+F_{m-1}\times F_{k+1}+ F_{m-1}\times F_k\\& =\left(F_m \times F_{k+2}+F_{m-1}\times F_{k+1}\right)+\left(F_m \times F_{k+1}+F_{m-1}\times F_k\right)\\&=F_{k+1+m}+F_{k+m}\\&=F_{k+2+m}.\end{align}$$So, (2) holds for n=k+2. Hence, (2) holds for any positive integer n. This follows from 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} $$Let A=\begin{pmatrix}1&1\\1&0\end{pmatrix} . Then A^{(k+1)m}=A^{km}A^m and so$$ F_{(k+1)m}=F_{km}F_{m+1}+F_{km-1}F_m$By induction,$F_m$divides$F_{km}$and so$F_m$divides$F_{(k+1)m}\$.