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\geq 4$. Using mathematical induction correctly, prove that $a_n < 2^n$ for all n ∈ Z+
in basis step, i prove $p_1, p_2 p_3 p_4$. Is $p_4$ proved in basis step? I want to show my work;
Proof:
We prove this inequality by induction. Let P(n) denote $a_n\le 2^n$.
Basis Step:
We consider $P_1,P_2$ and $P_3$.
$a_1=1<2=2^1$ so $P_1$ is true. $a_2=1<4=2^2$ so $P_2$ is true. $a_3=1<8=2^3$ so $P_3$ is true.
$a_4=a_1+a_2+a_3=3<16=2^4$ so $P_4$ is true.
Could you help me for the inductive step?
Assuming that $a_{i} < 2^i$ for $i \in \{k, k-1, k-2\}$. where $k \ge 3$.
We want to show that $$a_{k+1} < 2^{k+1}$$
We will use the assumptions in the induction hypothesis:
\begin{align} a_{k+1}&=a_k + a_{k-1} + a_{k-2} \\ &< 2^k + 2^{k-1}+2^{k-2} \\ &= 7 \cdot 2^{k-2} \\ &\le 8 \cdot 2^{k-2} \end{align}
You just need to verify $P_1$ to $P_3$ for the base case as the induction step would have covered $P_4$ though there is no harm checking for more in the base case.