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.
Best Answer
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.