Sequences with strong inductional proof

Question

i have encountered an inductional proof example.Actually i know basic induction but i stuck in this question after basis step. Can anybody write the following steps by using STRONG induction. The question is:

The sequence $a_1, a_2, a_3,\ldots$ is defined by $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for $n \ge 4$. Using mathematical induction correctly, prove that $a_n < 2^n$ for all $n \in\Bbb Z^+$.

Answer 1

My attempt:

Base case: $n = 1,2,3,4$:

$1< 2$,

$1<4$,

$1<8$,

$3<16$

Now we assume that the statement hold for everything upto $n-1$, and prove $n$: $$a_{n} = a_{n-1} + a_{n-2}+ a_{n-3} < 2^{n-1} + 2^{n-2} + 2^{n-3} = 2^{n-3}(1+2+4) = 7\cdot 2^{n-3} < 8\cdot 2^{n-3} = 2^n $$

Answer 2

Base: $n=4$. Obviously, $a_4=1+1+1=3<2^2=4.$

Assume the statement is true for k such that $k\leq n$. Let's prove it for $n+1.$ $a_{n+1}=a_{n}+a_{n-1}+a_{n-2}\leq 2^n+2^{n-1}+2^{n-2}=2^{n-2}(4+2+1)=2^{n-2}(7)<2^{n-2}8=2^{n+3}$.