Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
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
up vote 6 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.