Induction help ($a_n \lt 2^n$)

Question

so I'm having trouble solving this question..

Define the sequence $a_0$, $a_1$, ... as $$ a_i = \begin{cases} 2, & \text{if $0 \le i \le 2$} \\ a_{i-1}+a_{i-2}+a_{i-3}, & \text{if $i>2$} \end{cases} $$ Using complete induction, prove that $a_n \lt 2^n$ for every inter $n\ge2$.

What I got is this so far:

Base case: $n=2$: $a_2=2$ $\lt$ $2^2=4$

So base case holds.

Induction Hypothesis: Suppose P(k) holds (i.e. $a_k\lt2^k$)

Induction Step: P(k+1) holds (i.e. $a_{k+1}\lt2^{k+1}$)

\begin{align} a_{k+1} & = a_{k+1-1}+a_{k+1-2}+a_{k+1-3} \\ & = a_{k}+a_{k-1}+a_{k-2} \\ & \lt 2^k+a_{k-1}+a_{k-2} \\ \end{align}

I am confused how I should finish off the proof from here. Can someone help please?

Answer 1

Since you are supposed to do this using strong induction, you are supposed to be assuming that $P(l)$ holds for each $l\leqslant k$. So:\begin{align}a_{k+1}&=a_k+a_{k-1}+a_{k-2}\\&\leqslant2^k+2^{k-1}+2^{k-2}\\&<2^k+2\times2^{k-1}\\&=2^k+2^k\\&=2^{k+1}.\end{align}