# Thread: Fibonacci, proof with induction

1. ## Fibonacci, proof with induction

Hello, I think I am getting stuck; I would really appreciate any help or advice!

Prove by induction that $\displaystyle {Fib}_n \geq 2^{n/2}$ for $\displaystyle n \geq 6$

To start , prove the base case of $\displaystyle n = 6$:

$\displaystyle {Fib}_6 = 8, 2^{6/2} = 8$ so $\displaystyle {Fib}_6 \geq 2^{6/2}$

Now assume $\displaystyle {Fib}_n \geq 2^{n/2}$ is true.

We can multiply both sides by $\displaystyle 2^{1/2}$ to get the $\displaystyle n+1$ term on the right side.

$\displaystyle 2^{1/2}{Fib}_n \geq 2^{(n+1)/2}$

This is where I think I'm not sure about what to do. What I had been thinking is: now try to show that $\displaystyle {Fib}_{n+1} \geq 2^{1/2}{Fib}_n$

so that we can conclude with $\displaystyle {Fib}_n \geq 2^{n/2} \Longrightarrow {Fib}_{n+1} \geq 2^{(n+1)/2}$.

I had been trying: It's true that $\displaystyle {Fib}_{6+1} \geq 2^{1/2}{Fib}_6$. If we add $\displaystyle {Fib}_n$ to both sides, we can get the n+2 term on the left. But then I wasn't sure if there is another step..? Or if I'm on the right track at all?

THANKS! for any help!!

2. Originally Posted by dill_day
Prove by induction that $\displaystyle {Fib}_n \geq 2^{n/2}$ for $\displaystyle n \geq 6$

To start , prove the base case of $\displaystyle n = 6$
the base case for this problem is actually n = 6 and n = 7, not just n = 6. (you'll see why later!) now suppose that n > 7 and that the claim is true

for all $\displaystyle 6 \leq k < n.$ then $\displaystyle F_n^2 = (F_{n-1} + F_{n-2})^2 \geq (2^{\frac{n-1}{2}} + 2^{\frac{n-2}{2}})^2=2^n \left(\frac{1}{\sqrt{2}} + \frac{1}{2} \right)^2 > 2^n.$ therefore: $\displaystyle F_n > 2^{\frac{n}{2}},$ and the induction is complete!

Remark: as you may have noticed, for n > 6, the inequality is strict, i.e. $\displaystyle F_n > 2^{\frac{n}{2}}.$ it's a good exercise to try to find a non-inductive solution as well!

3. Thank you for the response! I am not sure I follow along...

I think I understand why 6 and 7 are both part of the basis: $\displaystyle F_n = F_{n-1} + F_{n-2}$, so we first prove for n = 6 and 7, and then assume that the claim $\displaystyle F_{k-1} + F_{k-2} \geq 2^{k/2}$ for some arbitrary $\displaystyle k$ where $\displaystyle k > 7$ - because $\displaystyle k > 7 \Longrightarrow k-2 \geq 6$.

Now we want to use the assumption that $\displaystyle F_{k-1} + F_{k-2} \geq 2^{k/2}$ to prove that, if this assumption is true, $\displaystyle F_{k} + F_{k-1} \geq 2^{(k+1)/2}$ must also be true.

I'm having trouble figuring out where to start working towards this though... or, how squaring $\displaystyle F_n$ leads to $\displaystyle F_{n+1}$...

Thanks again for your help, and to anyone who can help me out!!