Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers) Question: I want to prove that $F_{kn}$ is a multiple of $F_n$. 
Approach: I have to deduce this result from the following results: 
$$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$$
I have shown the result by induction on $k$. I want to know if it's possible to prove it via induction on $n$ instead. I have tried but get into a mess. Is there anything I need to be careful about when choosing which variable to carry out the induction on?
Thanks. 
 A: In fact your formula can be written:
$$F_{n+k+1} = F_{k+1}F_{n+1} + F_{k}F_{n}$$
and this is symmetric on $k$ and $n$ so the same argument works also, (you can only change $k$ on $n$ and $n$ on $k$ and your first proof becomes an induction on $n$)
A: For $n,m\in\mathbb{Z}$ and $n>m>1$, we can use the identity 
$$
F_{n-m+1}F_m+F_{n-m}F_{m-1}=F_n\tag{1}
$$
to prove that for any $n,m\in\mathbb{Z^+}$ that $F_m$ divides $F_{nm}$ (i.e., $F_{nm}$ is a multiple of $F_m$). 
To accomplish this, fix $m\geq 1$ and induct on $n$. For each $n\geq 1$, let $S(n)$ denote the statement that $F_m$ divides $F_{mn}$. 
Base step: For $n=1, F_m$ is identical to $F_{m\cdot 1}$, so the former divides the latter and $S(1)$ is true.
Induction step: For some fixed $k\geq 1$, suppose that $S(k)$ is true, that is, $F_m$ divides $F_{mk}$, say, $qF_m=F_{mk}$. To be shown is that $S(k+1)$, namely, that $F_m$ divides $F_{m(k+1)}$. Using $(1)$, with $n$ replaced by $m(k+1)$, we have the following:
\begin{align}
F_{m(k+1)} &= F_{m(k+1)-m+1}F_m+F_{m(k+1)-m}F_{m-1}\\[0.5em]
&= F_{mk+1}F_m+F_{mk}F_{m-1}\\[0.5em]
&= F_{mk+1}F_m+qF_mF_{m-1}\tag{by $S(k)$, the ind. hyp.}\\[0.5em]
&= F_m(F_{mk+1}+qF_{m-1}),
\end{align}
and so $F_m$ divides $F_{m(k+1)}$ as well, proving that $S(k+1)$ follows, completing the inductive step.
By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. Since $m$ was arbitrary, this completes the solution. $\blacksquare$
