<s>[INST] Show by induction that $F_n \geq 2^{0.5 \cdot n}$, for $n \geq 6$ I have the following problem:

Show by induction that $F_n \geq 2^{0.5 \cdot n}$, for $n \geq 6$

Where $F_n$ is the $nth$ Fibonacci number. 

Proof
Basis
$n = 6$. 
$F_6 = 8 \geq 2^{0.5 \cdot 6} = 2^{\frac{6}{2}} = 2^3 = 8$
Induction hypothesis
Assume $F_n \geq 2^{\frac{n}{2}}$, for some $n \geq 6$.
Inductive step
Lets shows that $F_{n+1} \geq 2^{\frac{n + 1}{2}}$. 
We know that 


*

*$F_{n + 1} = F_n + F_{n - 1}$

*$2^{\frac{n + 1}{2}} > 2^{\frac{n}{2}}$

*$2^{\frac{n + 1}{2}} = 2^{\frac{n}{2} + \frac{1}{2}} = 2^{\frac{n}{2}} \cdot 2^{\frac{1}{2}} \leq 2^{\frac{n}{2}} \cdot 2 = 2^{\frac{n}{2}} + 2^{\frac{n}{2}}$
Since we have assumed that $F_n \geq 2^{\frac{n}{2}}$, then $$F_n + F_{n - 1} = F_{n + 1} \geq 2^{\frac{n}{2}} +  F_{n - 1} \geq 2^{\frac{n}{2}} +  F_{n - 1} + 2^{\frac{n}{2}} - F_n = 2^{\frac{n}{2}} + 2^{\frac{n}{2}} +  F_{n - 1} - F_n$$
The last inequality is true because $2^{\frac{n}{2}} - F_n$ is negative or $0$, since $F_n \geq 2^{\frac{n}{2}}$.

I have tried a lot of things, but I cannot figure out how to proceed and how to conclude that indeed $F_{n + 1} \geq 2^{\frac{n}{2}} \cdot 2^{\frac{1}{2}}$. I feel really stupid after trying for a long time to do this alone and not managing to do it.
 [/INST] Suppose we knew for 2 values of n $F_n \ge 2^{\frac n2}$ i.e for n = 6 and n = 7.
We know this holds for n=6 and n=7.
We also know that $F_{n+1} = F_{n} + F_{n-1}$
So we assume for some k and k-1 (7 and 6) $F_{k-1} \ge 2^{\frac {k-1}{2}}$ and $F_{k+1} \ge 2^{\frac {k+1}{2}}$
We know $F_{k} \ge F_{n-1}$
so $F_{k+1} \ge 2 \cdot F_{n-1}$
Using the assumption $F_{k+1} \ge 2 \cdot 2^{\frac {k-1}{2}} = 2^{\frac{k+1}{2}}$ as required.
EDIT: If you want a phrasing in the language of induction (propositional)
 $$P(k) = F_{n} \ge 2^{\frac{n}{2}} \mbox{ & } F_{n-1} \ge 2^{\frac{n-1}{2}}\\$$
We then prove:
$$
P(k+1) = F_{n+1} \ge 2^{\frac{n+1}{2}} \mbox{ & } F_{n} \ge 2^{\frac{n}{2}}$$
Above I proved the second from the first.
</s>