Proof by induction on Fibonacci numbers: show that $f_nmid 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.

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.