Question regarding the Fibonacci sequence

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