Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers)

Question

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.

Answer 1

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

Answer 2

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$