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.
Best Answer
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!