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.

  • 2
    $\begingroup$ 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.) $\endgroup$ Sep 8 '13 at 13:43
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 8 '13 at 13:44
  • 3
    $\begingroup$ Related : math.stackexchange.com/questions/60340/… $\endgroup$ Sep 8 '13 at 13:45
  • $\begingroup$ I don't think that works. The edit checks the stuff that has changed. Retyping won't help (as far as I know). $\endgroup$ Sep 8 '13 at 13:46

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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