Prove that $F_n$ is a multiple of $F_k$ given that n is a multiple of k, using the identity $F_{a+b+1}=F_{a+1}F_{b+1}+F_aF_b$

Question

I haven't been able to get very far in the problem at all because I can't figure out how to change it to the terms of the identity. All I have for the problem is $F_{kx}$ = $F_n$ and y$F_k$=$F_n$. But I don't understand what this has to do with the identity, where the numbers in the subscript are being added and which does not necessarily have multiples.

Answer 1

If $n$ is a multiple of $k$, we can write $n=km$ for some $m \in \mathbb{N}$.

We will prove that $F_n=F_{km}$ is a multiple of $F_k$ by induction on $m$.

$m=1$: then $F_n=F_k$ and clearly $F_n$ is a multiple of $F_k$.

Suppose now that $F_{k(m-1)}$ is a multiple of $F_k$ i.e. $F_{k(m-1)}=c F_k$

Now $$F_{km}=F_{k(m-1)+(k-1)+1}=F_{k(m-1)+1}F_{k-1+1}+F_{k(m-1)}F_{k-1}=F_{k(m-1)+1}F_{k}+cF_{k}F_{k-1}=F_k(F_{k(m-1)+1}+cF_{k-1})$$

therefore $F_n=F_{km}$ is a multiple of $F_k$.