Multiples in the Fibonacci Series


I got this problem from Rustan Leino, who got it from Carroll Morgan.

I solved it and wrote up my solution.


Prove that for any positive $K$, every $K$th number in the Fibonacci sequence is a multiple of the $K$th number in the Fibonacci sequence. More formally, for any natural number $n$, let $F(n)$ denote Fibonacci number $n.$ That is, $F(0) = 0,$ $F(1) = 1,$ and $F(n+2) = F(n+1) + F(n).$ Prove that for any positive $K$ and natural $n$, $F(nK)$ is a multiple of $F(K).$

Solution     Reveal