# 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, 2014 at 11:29
• Sep 24, 2014 at 11:39

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}$.
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\$.