Strong inductive proof for this inequality using the Fibonacci sequence.

Question

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?

Answer 1

Your proof is great. Here's how you would explicitly use strong induction. Note that you have already proved the base case for when $n=8$.

Induction Hypothesis: Assume that $F_n>2n$ holds true for all $n\in\{8,...,k\}$, where $k\ge8$.

It remains to prove the inequality true for $n=k+1$. Observe that: $$ \begin{align*} F_{k+1} &= F_k + F_{k-1} \\ &> 2k + 2(k-1) & \text{by the induction hypothesis} \\ &\ge 2k + 2(8-1) & \text{since } k \ge8 \\ &= 2k+14 \\ &> 2k+2 \\ &= 2(k+1) \\ \end{align*} $$ as desired. This completes the induction.

Answer 2

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.

Answer 3

We will change the indexing slightly to make it look like archetypal strong induction.

We show that if the result holds for all $i$ such that $8\le i \lt k$ then it holds at $k$.

Because it holds at for all such $i$, it holds in particular at $k-1$. Now argue as you did (with minor index shift) that since $F_{k-1} \gt 2(k-1)$ and $2\lt F_{k-2}$, we have $2k=2(k-1)+2\lt F_{k-1}+F_{k-2}=F_k$.

Of course we have not used the full strength of the induction hypothesis, but we have written out things in strong induction style.

Answer 4

$F_n > 2n$ if $n > 8$.

Proof:

Consider $F_n = F_{n-1} + F_{n-2}$

Thus,

$$F_{n+1} = F_n + F_{n-1}$$

The idea is to show:

$$F_{n+1} > 2n + 2$$

By strong induction, for $n > 8$ since $P(8)$ is true,

$$F_n > 2n$$

$$F_{n-1} > 2n + 2$$

$$F_{n+1} = F_{n} + F_{n-1} > 4n + 2$$

Lemma: $4n + 2 > 2n + 2$

Proof:

$$4n + 2 > 2n + 2$$

$$4n > 2n$$

$$4 > 2$$

Hence,

$$F_{n+1} > 2n + 2$$