Am I correct that this proof doesn't need strong induction?

Question

The sequence $a_n, n \in \mathbb{N}, n \geq 1$ is defined recursively as follows: $a_1 = a_2 = a_3 = 1, a_n = a_{n-1} + a_{n-2} + a_{n-3}, n \geq 4$. Prove by induction that $a_n < 2^n$.

My proof:

First step: For $n=4$, we have $a_4 = 1+1+1 < 2^4$, so it's correct for $n=4$.

Induction hypothesis: $a_m = a_{m-1} + a_{m-2} + a_{m-3}, \forall m \in \mathbb{N}$ such that $4 \leq m \leq k$.

Proof: $a_{k+1} = a_k + a_{k-1} + a_{k-2} < 2^{k+1}?$

$$a_{k+1} = a_k + a_{k-1} + a_{k-2} \stackrel{def. seq.}{=} (a_{k-1} + a_{k-2} + a_{k-3}) + a_{k-1} + a_{k-2} $$ $$ a_{k+1}= 2a_{k-1} + 2a_{k-2} + a_{k-3} < 2( a_{k-1} + a_{k-2} + a_{k-3}) $$ $$2( a_{k-1} + a_{k-2} + a_{k-3}) \stackrel{def. seq}{=} 2a_k \stackrel{ind. hyp.}{<}2 \cdot2^k = 2^{k+1}$$

So we conclude that $a_{k+1} < 2^{k+1}$. We also conclude that we didn't need to use strong induction because mathematical induction sufficed as we only used the induction hypothesis for $m=k$.

I have two questions:

1. Is my proof correct, with regards to notation and such? I'm especially worried about my induction hypothesis, our teacher didn't explain strong induction well so I want to know if my induction hypothesis uses strong induction correctly (even though we didn't need it in this particular case, I reckon)
2. Is it correct that we didn't need to use strong induction for this proof? This question is kind of a subset of question 1.

Answer 1

This should be a comment, but is too long to fit in the given space. Actually, you don't even need induction. The characteristic polynomial associated with the given sequence is $$ p(t)=t^3-t^2-t-1 $$ that has three distinct roots $\alpha,\beta,\gamma$, with one of them being real, say $\alpha$ (so $\beta$ and $\gamma$ are conjugates). By the theory of linear recurrence relations, $a_n$ has the explicit form $$ a_n = A\alpha^n+B\beta^n+C\gamma^n $$ where the absolute constants $A,B,C$ depend on the initial conditions $a_1=a_2=a_3=1$.
We have $p(t)(t-1)=t^4-2t^3+1$, hence $p\left(2-\frac{1}{8}\right)>0$ and $p\left(2-\frac{1}{4}\right)<0$, so $\alpha$ belongs to the interval $\left(2-\frac{1}{4},2-\frac{1}{8}\right)$. By Vieta's formulas, $\alpha\beta\gamma=1$, hence $$ \|\beta\|=\|\gamma\| \leq \frac{1}{\sqrt{2-\frac{1}{4}}}\leq 1 \leq \|\alpha\|$$ and $$ a_n \leq |A|\cdot\left(2-\frac{1}{8}\right)^n+2|\text{Re}\, B|. $$ You may now use the initial conditions to prove $|A|\leq\frac{1}{4}$ and $2|\text{Re}\,B|\leq\frac{4}{3}$. It follows that $$ a_n \leq \frac{1}{4}\left(2-\frac{1}{8}\right)^n+\frac{4}{3}.$$

Answer 2

Yes, your proof is correct. You have avoided using of strong induction by digging deeply into the recursion.

Some strong induction proofs require the induction hypothesis be right for any integer between the basis and $n$, but for this problem, if you use strong induction, you only need the induction hypothesis holds for three numbers $n-2$, $n-1$, and $n$. In my opinion, this is similar to what you have done, that is, using the recursion twice.