Problem
I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to prove my findings through strong induction.
What I found
I found that the inequality is true for all $n >= 8$.
My attempt at proving by induction
Basis: $2(8) < F_8$ = TRUE
Assume: $2(k) < F_k$
Show: $2(k) < F_k$ implies $2(k+1) < F_{k+1}$
$2(k+1) = 2k + 2 < F_k + F_{k-1} = F_{k+1}$
Thus
$2(k+1) < F_{k+1}$
Logic:
$2k < F_k$ by induction hypothesis
$2 < F_{k-1}$ because $F_{k-1}$ is at least $13$ when $k>=8$
$F_{k+1}$ is $F_k + F_{k-1}$.
Is my proof correct? Is this considered strong induction?
Best Answer
IIRC, strong induction is when the induction depends on more than just the preceding value. In this case, you use the hypothesis for $k$ but not for any earlier values. Instead, you use a much weaker result ($F_{k-1} > 2$) for the earlier value.
So, I would not call this strong induction.
If you use the hypothesis ($F_n > 2n$) for $both$ $k$ and $k-1$, the induction works because $F_k > 2k$ and $F_{k-1} > 2(k-1)$ together imply $F_{k+1} = F_k+F_{k-1} > 2k + 2(k-1) = 4k-2 > 2(k+1) $ when $k \ge 3$.
Note that the induction step works when $k \ge 3$ but the induction hypothesis is true only when $k \ge 8$. So the first case where you can do the induction is $k = 9$, because you use the truth for $k=8$ and $k=9$ to prove it for $k=10$.
I would call this moderate induction, since it depends on the previous two cases being true.