1
$\begingroup$

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$ \begin{equation} F_k \geq 4 * F_{(k - 3)} \end{equation} 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Theo Bendit Sep 24 '18 at 0:02
2
$\begingroup$

$$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}$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – grant2088 Sep 24 '18 at 0:38
  • $\begingroup$ Yes, we just use the recursive relation to expand $F_n$ $\endgroup$ – Mohammad Riazi-Kermani Sep 24 '18 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.