Prove That If $a$ Divides Fibonacci $F_n$ For Every $d \geq 1$

[Grupax]

let $F_{n}$ the nth fibonacci number. Prove that if $a \geq 2$ divide $F_{n}$ then for every $d \geq 1$ we have $$a^{d}\mid F_{a^{d-1}n}.$$ I think we can use the formula $$F_{kn}= \underset{i=1}{\overset{k}{\sum}} \dbinom{k}{i}F_{i}F_{n}^{i}F_{n-1}^{k-i}$$ and the well know property that if $b \mid c$ then $F_{b} \mid F_{c}$ but I haven't find the solution yet.

 

[PaulRS]

Yes, you are right indeed, it follows from $
F_{k\,n} = \sum_{j=1}^k \binom{k}{j} F_j\, F_n^j F_{n-1}^{k-j}
$ and inductive reasoning.

Simply pick $k := a$, $ n := a^{d-1}\,n$ in that equation above, then observe that $F_{a^{d-1}\,n}^j$ is a multiple of $a^{d+1}$ for $j\geq 2$ (use the inductive hypothesis here), while, for $j = 1$, we have $\binom{a}{1} = a$ and $a^{d} | F_{a^{d-1}\,n}$. This proves that if $a^d | F_{a^{d-1}\,n}$, then $a^{d+1} | F_{a^d\,n}$.