Given the sequence $a_0=1, a_1=2, a_2=3, a_n=a_{n-1}+a_{n-2}+a_{n-3}$, prove by strong induction that for $n\geq 0, a_n \leq 2^n$

Question

I've been trying to work this out for some time and I keep getting stuck. Here is what I have thus far:

Base Case:

$n=0 ; 1 \leq 1$

$n=1 ; 2 \leq 2$

$n=2 ; 3 \leq 4$

Induction hypothesis:

Assume property holds for $4 \leq n \leq k$

$a_k = a_{k-1}+a_{k-2}+a_{k-3}$

Induction Step:

$a_{k+1} = a_k+a_{k-1}+a_{k-2} \leq 2^{k+1}$

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

$ a_{k+1} = 2(a_{k-1}+a_{k-2}) + a_{k-3} \leq 2^k * 2$

This is where I am stuck, and not entirely sure I'm on the right track. A nudge in the right direction would be greatly appreciated!

Answer 1

Hint: $$ a_n = a_{n-1} + a_{n-2} + a_{n-3} \leq 2^{n-1} + 2^{n-2} + 2^{n-3} = 2^n - 2^{n-3} < 2^n. $$

Answer 2

You can trace in this way:

$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} \leq 2^{n-1} + 2^{n-2} + 2^{n-3} = \frac12 2^n + \frac142^{n} + \frac18 2^n= \frac78 2^n< 2^n. $$

Answer 3

Be careful with your proof as it is; you cannot assume that $a_{k+1}\leq2^{k+1}$ in order to prove that fact. Anyway, by rewriting $a_k$, we have

$a_{k+1} = a_k+a_{k-1}+a_{k-2}=2a_{k-1}+2a_{k-2}+a_{k-3}\leq2(a_{k-1}+a_{k-2}+a_{k-3})=2a_k$

I think you can finish it from here.