Then $F_a$ divides $F_{an}$, $n \in \Bbb{N}$ where $F_i$ denotes the $i$-th Fibonacci number.

Question

Let $a$ be a fixed natural number. Then $F_a$ divides $F_{an}$, $n \in \Bbb{N}$ where $F_i$ denotes the $i$-th Fibonacci number.

For $n=1$ the result is true. Let it be true for $n=k$.

$$\begin{align}F_{ka+a} &= F_{ka+(a-1)} + F_{ka+(a-2)} \\ &= 2F_{ka+(a-2)} + F_{ka+(a-3)}\\ &= 3F_{ka+(a-3)} + 2F_{ka+(a-4)}\\ &= 5F_{ka+(a-4)} + 3F_{ka+(a-3)} = ...\\ &= F_aF_{ka+1} + F_{a-1} F_{ka}\end{align} $$

Thus $F_a$ divides $F_{(k+1)a}$. Hence the result is true by induction.

Is the proof correct?

Answer 1

To avoid the dots in your proof, show by (strong) induction with respect to $n$, that a more general identity holds: $$F_{n+m+1}=F_{m+1}F_{n+1}+F_{m}F_{n}.$$ Then apply it for $m=a-1$ and $n=ka$, to find directly what you need $$F_{ka+a} = F_aF_{ka+1} + F_{a-1} F_{ka}.$$ For the inductive step: $$\begin{align} F_{n+m+2}&=F_{n+m}+F_{n+m+1}\\ &=(F_{m+1}F_{n}+F_{m}F_{n-1})+(F_{m+1}F_{n+1}+F_{m}F_{n})\\ &=F_{m+1}(F_n+F_{n+1})+F_m(F_{n-1}+F_n)\\ &=F_{m+1}F_{n+2}+F_mF_{n+1} \end{align}$$

Answer 2

The outer induction is good if the inner one is, but the inner induction is rather hand-wavy. Pull it out as a lemma and state it precisely. It may be worth generalising to $F_{m+n}$ in terms of $F_m$ and $F_n$.