# Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem:

The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation-

$$f_n = f_{n-1} + f_{n-2}$$ with $$f_1 = f_2 = 1$$

Use induction to show that $$f_n \; | \; f_{2n}$$ ($$f_n$$ divides $$f_{2n}$$)

Basis Step is obviously true; but I'm facing difficulty in the Inductive Step. If I assume the inductive hypothesis to be true for some $$k$$, i.e., $$\dfrac{ f_{2k} } { f_{k} } = c$$ (For some positive integer $$c > 0$$), I'm not clear as to how I should proceed further and prove that $$P(2k+1)$$ is also true.

I'm new here, so if I'm doing anything wrong, please overlook it on the account of my naivety.

• Try looking at some small examples to see what's going on — sometimes you have to strengthen your induction hypothesis and prove a stronger statement. (And also, there are easy ways of proving this statement without induction of course, but in this context I guess what you want/need is a proof by induction.) – ShreevatsaR Sep 8 '13 at 13:43
• @Tarun, please correct the typo where I wrote $\dfrac{ f_{2k} } { f_{2k} } = c$ instead of $\dfrac{ f_{2k} } { f_{k} } = c$. I am not able to edit since the edit requires 6 characters to be changed at least. – Parth Thakkar Sep 8 '13 at 13:44
• – lab bhattacharjee Sep 8 '13 at 13:45
• I don't think that works. The edit checks the stuff that has changed. Retyping won't help (as far as I know). – Parth Thakkar Sep 8 '13 at 13:46

Hint: Look at the sequence of values of $\frac{f_{2k}}{f_k}$. Do you see a pattern there? That suggests to prove the following fact:
$$\frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} }$$
Check that the first two terms of this series $g_n = \frac{f_{2n}}{f_n}$ are integers, hence conclude by induction that every term is an integer.
We know that $f_n \wedge f_m=f_{n\wedge m}$, where $a\wedge b$ is the gcd of $a$ and $b$. So $f_n \wedge f_{2n}=f_{n\ \wedge\ 2n}=f_n$. This means that $f_n$ divides $f_{2n}$.