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