Fibonacci, proof with induction

Printable View

August 26th 2008, 06:38 PM
dill_day

Fibonacci, proof with induction

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

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

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

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

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

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

$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 ${Fib}_{n+1} \geq 2^{1/2}{Fib}_n$

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

I had been trying: It's true that ${Fib}_{6+1} \geq 2^{1/2}{Fib}_6$ . If we add ${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!!
August 26th 2008, 10:25 PM
NonCommAlg

Quote:

Originally Posted by dill_day

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

To start , prove the base case of $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 $6 \leq k < n.$ then $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: $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. $F_n > 2^{\frac{n}{2}}.$ it's a good exercise to try to find a non-inductive solution as well!
August 27th 2008, 10:19 AM
dill_day

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: $F_n = F_{n-1} + F_{n-2}$ , so we first prove for n = 6 and 7, and then assume that the claim $F_{k-1} + F_{k-2} \geq 2^{k/2}$ for some arbitrary $k$ where $k > 7$ - because $k > 7 \Longrightarrow k-2 \geq 6$ .

Now we want to use the assumption that $F_{k-1} + F_{k-2} \geq 2^{k/2}$ to prove that, if this assumption is true, $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 $F_n$ leads to $F_{n+1}$ ...

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