# 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.

• You should take as hypothesis that both $F_n\ge2^{n/2}$ and $F_{n+1}\ge2^{(n+1)/2}$. Then show that $F_{n+2}\ge2^{(n+2)/2}$. – Aretino Aug 1 '15 at 23:17
• @Aretino I have never seen taken as hypothesis 2 things for different $n$s... why should that be even possible or correct? – nbro Aug 1 '15 at 23:20
• Why not? If you think of it, the reasoning is exactly the same as in the simple case. See also the answers you got and here: en.wikipedia.org/wiki/Mathematical_induction#Complete_induction. – Aretino Aug 2 '15 at 7:26

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}$$

• But you cannot use the fact that $F_{n - 1} \geq 2^{\frac{n - 1}{2}}$, since I have not assumed it anywhere. – nbro Aug 1 '15 at 23:18
• Ok, but there is a strong induction that you could use. – Euler88 ... Aug 1 '15 at 23:23
• I was trying to use strong induction, as you may have noticed from my reasoning, but I failed... – nbro Aug 1 '15 at 23:24
• You can make like that: Suppose that $f_k\geq 2^{k/2}$ for all $k\leq n$ and then try to prove for $f_{n+1}$. – Euler88 ... Aug 1 '15 at 23:26

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.