Induction Proof possible here?

Question

The Fibonacci numbers are defined by

$F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$, for $n\ge 2$.

Is it possible to prove by induction that $F_n\ge 4F_{n-3}$ for $n\ge 5$?

Answer 1

Yes, but you'll have to use complete (or strong) induction.

Step 1: Check that $F_5 \geq 4 F_2$ and $F_6 \geq 4 F_3$.

Step 2: Assume that the inequality $F_k \geq 4 F_{k-3}$ holds for all integers $k$ less than $n$. Using this assumption and the recursion $F_{n+1}=F_n+F_{n-1}$ one can quickly show that $$F_{n+1} \geq 4 F_{(n+1)-3}.$$ I'll leave the pleasure to write this down to you.

Step 3: By the principle of complete induction, the inequality holds for all $n \geq 5$.