I want to show that for the Fibonacci numbers, $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6.
My thought was to prove this via induction.
I showed the base case is true for $F_n$, n=6 and 7.
I assumed this was true for $F_{n-1}$, and $F_n$
=> $F_{n-1}$ >= $2^{\frac{n-1}{2}}$ and $F_{n}$ >= $2^{\frac{n}{2}}$
=> $F_{n+1}$ = $F_{n-1}$ + $F_{n}$
=> $F_{n+1}$ = $2^{\frac{n-1}{2}}$ + $2^{\frac{n}{2}}$
=> $F_{n+1}$ = $2^{\frac{n-1}{2}}$ $( 1 +$ $2^{\frac{1}{2}}$)
But in order to have $F_{n+1}$ >= $2^{\frac{n+1}{2}}$ I need $( 1 +$ $2^{\frac{1}{2}}$) >= 4, which is not true. This is where I get stuck.
Can anyone offer some tips? Thanks.
There is an arithmetic error. You have $2^{(n+1)/2}=2\cdot2^{(n-1)/2}$, so for your induction step to work as intended it suffices to check that $1+2^{1/2}\ge2$?