Induction of a recursively define sequence

Question

I am stuck on this problem at the induction step. Here is what I have done so far.

Problem: $a_0 = 0,\ a_1 = 1,\ a_2 = 2$ and $a_n = a_{n-1} + a_{n-2} + 2a_{n-3}$.

Show that for all $n \in \mathbb{N}$, that $a_n \leq 2^n$.

The base cases ($a_0$, $a_1$, $a_2$) are all obviously true.

Assuming $n = k$ gives: $a_{k-1} + a_{k-2} + 2a_{k-3} \leq 2^k$.

I need to show it works for $n = k+1$:

$$a_{k-1 + 1} + a_{k-2 + 1} + 2a_{k-3 +1} \leq 2^{k+1}.$$

I'm not sure how to approach this now, so any push in the right direction would be greatly appreciated.

Answer 1

Strong induction. Inductive hypothesis: $$a_n<2^n, a_{n-1}<2^{n-1}, a_{n-2}<2^{n-2}.$$ Inductive step: $$a_{n+1}=a_n+a_{n-1}+2a_{n-2}<2^n+2^{n-1}+2\cdot 2^{n-2}=2^n\left(1+\frac12+\frac12\right)=2^{n+1}.$$

Answer 2

Since you want to combine $a_{n-1},a_{n-2},a_{n-3}$ you're better off using strong induction than weak induction. If you just assume that the theorem is true for all $k<n$ instead of assuming it's true for $n-1$, it will fall into your lap.

Try it.