6
$\begingroup$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$

My Proof:

Base case: $n = 1$

$\operatorname{fibonacci}(1) \le 2^ 1$ is $1 \le 2$, true.

Base case holds

Inductive Hypothesis:

Assume true for $n = k$: $\operatorname{fibonacci}(k) \le 2^k$

Show True for $\operatorname{fibonacci}(k+1) \le 2^{k+1} $

$$\operatorname{fibonacci}(k) * k \le 2^k k$$ $$\operatorname{fibonacci}(k) \le 2^{k+1} $$ I get stuck here

Any help?

$\endgroup$
  • 1
    $\begingroup$ Try using strong induction, i.e. assume $F_k \le 2^k$ for all $k \le n$ and then prove that $F_{n+1} = F_n + F_{n-1} \le 2^{n+1}$. $\endgroup$ – JimmyK4542 Aug 12 '14 at 5:13
  • $\begingroup$ is it possible through simple induction, because we have not been introduced to "strong induction" ? @JimmyK4542 $\endgroup$ – user3343972 Aug 12 '14 at 5:16
  • 3
    $\begingroup$ Actually, if you know that all fibbonacci numbers are increasing, you can say $F_{n+1} = F_n + F_{n-1} \le F_n + F_n = 2F_n$. $\endgroup$ – JimmyK4542 Aug 12 '14 at 5:18
  • $\begingroup$ for instance, f(n) = f(n-1) + f(n -2), can I sub in k+1 for n and get to f(k) + f(k-1)? @JimmyK4542 $\endgroup$ – user3343972 Aug 12 '14 at 5:20
  • $\begingroup$ @user36829 How is this a duplicate? That's a different problem. $\endgroup$ – user147263 Aug 12 '14 at 5:24
5
$\begingroup$

Assume that:

All Fibonacci numbers are positive. $(\star)$

Then observe that: \begin{align*} \text{fibonacci}(k + 1) &= \text{fibonacci}(k) + \text{fibonacci}(k - 1) \\ &< \text{fibonacci}(k) + \text{fibonacci}(k - 1) + \text{fibonacci}(k - 2) &\text{by }(\star)\\ &= \text{fibonacci}(k) + \text{fibonacci}(k) \\ &= 2 \cdot \text{fibonacci}(k) \\ &\leq 2 \cdot 2^{k} &\text{by the ind. hypothesis} \\ &= 2^{k + 1} \end{align*} as desired. $~~\blacksquare$

$\endgroup$
  • $\begingroup$ This proof silently assumes that k >= 2. But the other cases can be done by hand. $\endgroup$ – Blaisorblade Jan 19 at 12:39
4
$\begingroup$

It is clear in the base case that $F_1\le 2^1$ and $F_2\le 2^2$. Then in the inductive step we see that \begin{align} F_n &= F_{n-1}+F_{n-2}\\ &\le 2^{n-1} + 2^{n-2}\\ &= 2^{n-2}(2 + 1)\\ &\le 2^{n-2}(4)\\ &=2^n. \end{align}

$\endgroup$
  • $\begingroup$ Don't we need P(k+1) -> 2^k+1 at the end of the proof? @fahrbach $\endgroup$ – user3343972 Aug 12 '14 at 14:20
  • $\begingroup$ Not really, but we need some sort of advancement with the indices. We could have written $F_{n+1} = F_{n} + F_{n-1}$ instead, but the idea is the same. Notice in this answer that we prove the hypothesis for $F_3$, then $F_4$, etc. $\endgroup$ – fahrbach Aug 12 '14 at 15:51
4
$\begingroup$

For the first term, we have $$F_1=1<2^1$$ Now assume the statement is true for $F_n$, the $nth$ Fibonacci term i.e. $$F_n\le2^n$$ Then, we have for $F_{n+1}$ $$F_{n+1}=F_n+F_{n-1}$$ Since this is a strictly increasing sequence, we know that $$F_n>F_{n-1}$$ and since $$2F_n=F_n+F_n$$ we also have that $$2F_n>F_n+F_{n-1}$$ We already know (by assumption) that $$F_n\le2^n$$ $$\Rightarrow 2F_n\le2^{n+1}$$ Combining these inequalities, we have $$2^{n+1}\ge2F_n>F_{n+1}$$ $$\Rightarrow2^{n+1}\ge F_{n+1}$$ $$\Rightarrow F_n\le2^n$$

$\endgroup$
1
$\begingroup$

For $n = 1$, see that it holds: $1 = F_1 < 2^1$.

Assume that $F_k < 2^k$. Since $F_{k+1} = F_k + F_{k - 1} < 2^k + 2^{k - 1} < 2^{k + 1}$, as desired.

$\endgroup$
0
$\begingroup$

Consider the more general problem: For which $a,b>0$ do we have $F(n) \le ab^n$ ?

The natural induction argument goes as follows: $$ F(n+1) = F(n)+F(n-1) \le ab^n + ab^{n-1} = ab^{n-1}(b+1) $$ This argument will work iff $b+1 \le b^2$ (and this happens exactly when $b \ge \phi$).

So, in your case, you can take $a=1$ and you only have to check that $b+1 \le b^2$ for $b=2$, which is immediate.

This only takes care of the induction step. You still need the base cases, $n=0$ and $n=1$, and so we need $a\ge0$ and $ab\ge1$.

$\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.