# Strong Inductive proof for inequality using Fibonacci sequence

I am trying to prove that $$F_n \geq 4 * F_{(n - 3)}$$ using the Fibonacci sequence, I think it the proof requires strong induction but I am unsure of how to apply it.

My work so far:

Define the Fibonacci numbers by:

\begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{(n-1)} + F_{(n-2)} \forall n \geq 2 \end{align*}

1. Prove by induction that $$F_n \geq 4 * F_{(n - 3)}$$

Base case: $$n = 5$$

\begin{align*} F_5 &\geq 4 * F_{(5 - 3)} \\ F_5 &\geq 4 * F_{(2)} \\ F_5 &\geq 4 * 1 \\ 5 &\geq 4 \end{align*}

Suppose true for some $$n = k$$ $$$$F_k \geq 4 * F_{(k - 3)}$$$$ Inductive step: Consider case $$n = k + 1$$

\begin{align*} F_{(k + 1)} &\geq 4 * F_{(k + 1 - 3)} \\ F_{(k + 1)} &\geq 4 * F_{(k - 2)} \end{align*}

The $$F_{(k - 2)}$$ makes me think the of the Fibonacci definition and that it should be possible if I use $$n = 5, 6$$ in the base case. However I am not sure what the next step should be so I can go further.

EDIT:

So thanks to Mohammad Riazi-Kermani I was able to go further. Since the Fibonacci sequence is defined as a recurrence relation, I can use the preceding terms to manipulate the expression. i.e. \begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_2 &= F_1 + F_0 \\ F_3 &= F_2 + F_1 \\ F_4 &= F_3 + F_2 \\ \text etc. \end{align*}

So following the pattern \begin{align*}\\ F_n &= F_{(n-1)} + F_{(n-2)}\\ F_{(n-1)} &= F_{((n-1)-1)} + F_{((n-1)-2)}\\ &= F_{(n-2)} + F_{(n-3)}\\ F_{(n-2)} &= F_{((n-2)-1)} + F_{((n-2)-2)}\\ &= F_{(n-3)} + F_{(n-4)}\\ F_n &= F_{(n-2)} + F_{(n-3)} + F_{(n-3)} + F_{(n-4)} \end{align*}

Now I have $$F_n = 3*F_{(n-3)} + 2*F_{(n-4)}$$ which allows me to get to the hint pointed out by Theo Bendit.

\begin{align*} 3*F_{(n-3)} + 2*F_{(n-4)} &\geq 4*F_{(n-3)}\\ 2*F_{(n-4)} &\geq F_{(n-3)} \end{align*}

But what does this mean since I did not have to do the inductive step?

EDIT 2:

It seems I am confusing the inductive hypothesis (assuming $$P(k)$$) with $$P(k + 1)$$.

So true for all $$n \geq 5$$ by principle of mathematical induction. Q.E.D.

• Hint: by playing around with the recurrence relation, you can show $F_n = 3F_{n-3} + 2F_{n-4}$. So, if you can show $2F{n-4} \ge F_{n-3}$, then you're done. If you play around further, you can show that this is equivalent to the Fibonacci sequence increasing. Sep 24, 2018 at 0:02

$$F_n=F_{n-1}+F_{n-2}$$
$$=F_{n-2}+F_{n-3}+F_{n-3}+F_{n-4}$$
$$=3F_{n-3}+2F_{n-4} \ge 3F_{n-3}+F_{n-4}+F_{n-5}$$
$$=4F_{n-3}$$
• So you can increase the sequence based on the recursive definition of the Fibonacci sequence. On the second line I assume that’s what you did by letting $n = n - 1$, is that fair? Is a let statement needed? Sep 24, 2018 at 0:38
• Yes, we just use the recursive relation to expand $F_n$ Sep 24, 2018 at 1:36