# Prove by induction that $Fib_{n} \geq (3/2)^{n-1}$

I need help with the last inductive steps, can someone help? I hope my formatting is good enough, first time here.

The case:

"Let the fibonacci sequence be recursivly defined so that $$F_0 = 0, F_1 = 1$$ Else if n >= 2 $$F_n = F_{n-1}+F_{n-2}$$ Prove that $$F_n \geq (3/2)^{n-1}$$ For all numbers in the set $$\{6,7,8,9...\}$$"

Basecase: $$F_{2} = F_{1} + F_{0} = 1 + 0$$ $$F_{3} = F_{2} + F_{1} = 1 + 1$$ $$F_{4} = F_{3} + F_{2} = 2 + 1$$ $$F_{5} = F_{4} + F_{3} = 3 + 2$$ $$F_{6} = F_{5} + F_{4} = 5 + 3$$

$$F_{6} \geq (3/2)^{5} = 8 \geq 7.59$$

Induction step:

We assume the above is true for $$n=k$$, so now we prove it is true for $$n=k+1$$

We remember $$F_n \geq (3/2)^{n-1}$$

$$F_{k+1} \geq (3/2)^{k}$$

We know that

$$F_{k} = F_{k-1}+F_{k-2}$$ $$F_{k+1} = F_{k}+F_{k-1}$$ $$F_{k}+F_{k-1} \geq (3/2)^{k}$$

I'm not quite sure where to go from here, can anyone help? I've looked at another thread about the same question, but I don't understand the last part of his equation nor the answers.

In my case we are told that "you may need to use $$(3/2)+1 > (3/2)^{2}$$", but I don't know how to apply it to my case.

• – lhf Oct 25 '18 at 11:29
• Ihf, thanks but I already read that actually. Inside the link I post there's also a direction to that exact answer, but I couldn't understand it. However, José's answer makes perfect sense to me and is very intuitive - to me atleast! – jubibanna Oct 25 '18 at 14:24

## 2 Answers

If $$F_k\geqslant\left(\frac32\right)^{k-1}$$ and $$F_{k+1}\geqslant\left(\frac32\right)^k$$, then\begin{align}F_{k+2}&=F_k+F_{k+1}\\&\geqslant\left(\frac32\right)^{k-1}+\left(\frac32\right)^k\\&=\left(\frac32\right)^{k-1}\left(1+\frac32\right)\\&>\left(\frac32\right)^{k-1}\left(\frac32\right)^2\\&=\left(\frac32\right)^{k+1}.\end{align}

• Thanks, this makes very much sense! <3 – jubibanna Oct 25 '18 at 10:45
• José, how can $(3/2)^{k-1} + (3/2)^{k}$ be equal to $(3/2)^{k-1}(1+3/2)$ ? – jubibanna Oct 25 '18 at 14:33
• I did not claim that they are equal. What I claimed was that$$\left(\frac32\right)^{k-1}+\left(\frac32\right)^k=\left(\frac32\right)^{k-1}\left(1+\frac32\right).$$ – José Carlos Santos Oct 25 '18 at 14:34
• Sorry, just edited my question. How did you find it's the same? – jubibanna Oct 25 '18 at 14:38
• \begin{align}\left(\frac32\right)^{k-1}+\left(\frac32\right)^k&=\left(\frac32\right)^{k-1}+\left(\frac32\right)^{k-1}\times\frac32\\&=\left(\frac32\right)^{k-1}\left(1+\frac32\right).\end{align} – José Carlos Santos Oct 25 '18 at 14:45

Write $$F_{k+1}\geq (3/2)^k+(3/2)^{k-1}=(3/2)^{k-1}(1+3/2)$$ from here you can finish using the hint.

• Thanks for the reply, it helped me to make sense of it all! – jubibanna Oct 25 '18 at 10:45
• No problem, I am happy it was helpfull – Madarb Oct 25 '18 at 10:48