2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.