2
$\begingroup$

I need to prove the n-th Fibonacci number is less than $2^n$ for all $n \geq 0$ using strong induction.

I have been exposed to the idea that strong induction differs from weak induction in that the pattern upon which induction is based often does not repeat at every value of $n$. ( For example, the nth term in a sequence might be defined in terms of the $n - 4$th term, as opposed to the $n - 1$ term, "reaching back four terms" as it were. )

The Fibonacci sequence "reaches back" two terms. So, I show for two base cases that the predicate is true for $n = 0$ and $n = 1$:

$ \begin{align} F_0 &= 1 \leq 2^0 \\ F_1 &= 1 \leq 2^1 \\ \end{align} $

Then, I state the inductive hypothesis:

$ \left(\ \forall\ k \in \mathbb{N} \cup \left\{ 0 \right\} \ \right) \left(\ F_k = F_{k-1} + F_{k-2} \leq 2^k \ \right) $

From there, I step forward twice:

$ \left(\ \forall\ k \in \mathbb{N} \cup \left\{ 0 \right\} \ \right) \left(\ F_k = F_{k-1} + F_{k-2} \leq 2^k \ \right) \\ \left(\ \forall\ k \in \mathbb{N} \cup \left\{ 0 \right\} \ \right) \left(\ F_{k+1} = F_{k} + F_{k-1} \leq 2^{k+1}\ \right) \\ \left(\ \forall\ k \in \mathbb{N} \cup \left\{ 0 \right\} \ \right) \left(\ F_{k+2} = F_{k+1} + F_{k} \leq 2^{k+2}\ \right) \\ $

And from there--I think--I should be able to do some substitution or other simple arithmetic operation to show that the inductive step is true if any base case is true.

But, I'm just not seeing it.

Any help would be appreciated.

$\endgroup$
5
  • $\begingroup$ Hint: $F_k=F_{k-1}+F_{k-2}<2^{k-1}+2^{k-2}=2^{k-2}(2+1)<2^{k-2}(4)$ $\endgroup$ Commented Jun 29, 2016 at 0:37
  • 2
    $\begingroup$ $F_{n+1} = F_{n} + F_{n-1} < 2^n+2^{n-1} < 2^n+2^n=2^{n+1} $. Strong induction comes in play in that we must assume not only is this true for F_n but for F_{n-1} as well. $\endgroup$ Commented Jun 29, 2016 at 0:41
  • $\begingroup$ (You are not stating the inductive hypothesis correctly.) $\endgroup$ Commented Jun 29, 2016 at 0:46
  • $\begingroup$ Related to math.stackexchange.com/questions/951111/… $\endgroup$ Commented Jun 29, 2016 at 1:10
  • $\begingroup$ Possible duplicate of math.stackexchange.com/questions/894743/…. $\endgroup$ Commented Jun 29, 2016 at 1:11

2 Answers 2

Reset to default
2
$\begingroup$

Now, I'm going to restate what you said in the induction step, but simplify it more. The first statement was: $$F_k \leq 2^k$$ Notice how I left out the $\forall$ part. This is because you only add that in until after you've proven the statement. The second statement was: $$F_{k+1} \leq 2^{k+1}$$ The third statement was: $$F_{k+2} \leq 2^{k+2}$$ We assume the first two statements are true. Now, by the definition of the Fibonacci sequence, we know that: $$F_{k+2}=F_{k+1}+F_k$$ This means we need to add $F_k$ and $F_{k+1}$ to get an inequality somehow. We do this by adding the first two statements together: $$F_k+F_{k+1} \leq 2^k+2^{k+1} \implies F_{k+2} \leq 2^k+2^{k+1}$$ Now, I'll let you take it from here. Good luck!

$\endgroup$
3
  • 2
    $\begingroup$ Pardon my French, but--you glorious bastard, I love you! Understandable, concise, direct. Thank you! $\endgroup$ Commented Jun 29, 2016 at 1:15
  • 4
    $\begingroup$ That is the weirdest compliment I have ever seen on this site. $\endgroup$ Commented Jun 29, 2016 at 1:16
  • $\begingroup$ It's probably also weird that I take that as a compliment. :D $\endgroup$ Commented Jun 29, 2016 at 1:17
0
$\begingroup$

Not Directly an Inductive Proof

Let $n\geq 2$ be an integer. Note that $F_n$ is the number of binary sequences of length $n-2$ without consecutive occurrences of $1$ (this part can be proven by induction). Since there are in total $2^{n-2}$ binary sequences of length $n-2$, it follows that $F_n\leq 2^{n-2}$. The equality holds only when $n=2$ and $n=3$.

Now, $F_0=0<1=2^0$, $F_1=1<2=2^1$, and $F_n\leq 2^{n-2}<2^n$ for all integer $n\geq 2$. The claim that $F_n<2^n$ for every integer $n\geq 0$ follows.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.