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

Question

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.

Answer 1

We have that $F_n>F_{n-1}$ then $$F_{n+1}=F_n+F_{n-1}>2F_{n-1}>2\cdot2^{(n-1)/2}=2^{(n+1)/2}$$

Answer 2

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.