3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Aretino Aug 1 '15 at 23:17
  • $\begingroup$ @Aretino I have never seen taken as hypothesis 2 things for different $n$s... why should that be even possible or correct? $\endgroup$ – nbro Aug 1 '15 at 23:20
  • $\begingroup$ 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. $\endgroup$ – Aretino Aug 2 '15 at 7:26
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ But you cannot use the fact that $F_{n - 1} \geq 2^{\frac{n - 1}{2}}$, since I have not assumed it anywhere. $\endgroup$ – nbro Aug 1 '15 at 23:18
  • $\begingroup$ Ok, but there is a strong induction that you could use. $\endgroup$ – Euler88 ... Aug 1 '15 at 23:23
  • $\begingroup$ I was trying to use strong induction, as you may have noticed from my reasoning, but I failed... $\endgroup$ – nbro Aug 1 '15 at 23:24
  • $\begingroup$ 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}$. $\endgroup$ – Euler88 ... Aug 1 '15 at 23:26
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.