Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
1  
@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
3  
    
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
add comment

1 Answer 1

up vote 4 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|improve this answer
add comment

Your Answer

 
discard

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.