Prove $a_n < 2^n$ using strong induction

Question

Prove: $a_n < 2^n$ for all $n\ge 1$

$a_n = a_{n-1} + a_{n-2} + a_{n-3},\quad n\ge4$

$a_1=1 , a_2=2 , a_3=3$

Answer 1

I will assume that you can provide a proper induction basis, so I'll leave that to you.

Using strong induction, our induction hypothesis becomes:

• Suppose that $a_k<2^k$, for all $k\leq n$.

In the induction step we look at $a_{n+1}$. We write it out using our recursive formula and see that: $$a_{n+1}=a_n+a_{n-1}+a_{n-2}.$$ Now by the induction hypothesis we know that:

• $a_n<2^n$,
• $a_{n-1}<2^{n-1}$, and
• $a_{n-2}<2^{n-2}$.

So $a_{n+1}<2^n+2^{n-1}+2^{n-2}$. Some basic airithmetic will lead to the final statement now.