# 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

## 2 Answers

From the start, there isn't a clear statement to induct on. As such, you have to guess the induction hypothesis, and find an explicit pattern which you could describe.

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.

The question is old, Calvin Lin's answer is great and already accepted but here is another method (for the famous sake of completess):

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}$.