# Question about strong induction

Let $$a_1,a_2,a_3,\cdots$$ be the sequence of integers defined by $$a_1=1$$, $$a_2=3$$, $$a_3=7$$ and$$a_i=a_{i−1}+a_{i−2}+a_{i−3}$$ for each integer $$i≥4$$. Prove by strong induction that $$a_n<2^n$$ for all integers $$n≥1$$.

To be honest, I don't really understand the concept of strong induction like what is the difference between strong and normal induction. Based on the question above I have already done a base case:

• When $$n = 1$$, $$a_i = 1$$ and $$1<2^1$$ therefore true for $$n = 1$$.
• When $$n = 2$$, $$a_i = 3$$ and $$3<2^2$$ therefore true for $$n = 2$$.
• When $$n = 3$$, $$a_i = 7$$ and $$7<2^3$$ therefore true for $$n = 3$$.

However, I am not too sure about the induction step. I am a bit confused on how to implement this statement ($$a_i = a_{i−1} + a_{i−2} + a_{i−3}$$ for each integer $$i ≥ 4$$) into the induction. What approach should I take to prove the statement is true?

The difference between regular induction and strong induction is that in regular induction you assume some predicate $$P$$ is true of $$k$$, then show from this that $$P$$ is true of $$k+1$$. Along with a base case this proves the predicate is true for all naturals. In strong induction you assume $$P$$ is true for all naturals less than or equal to $$k$$ and prove it for $$k+1$$.
In this problem your equation involves $$a_{n-1}, a_{n-2},$$ and $$a_{n-3}$$. You want to use the fact that $$a_k \lt 2^k$$ for each of them. This is what makes it strong induction as you use three instances of the induction hypothesis. So assume $$a_k \lt 2^k$$ for all $$k \lt n$$ and say $$a_n=a_{n-1}+a_{n-2}+a_{n-3}\\ \lt 2^{n-1}+2^{n-2}+2^{n-3}\\ =7\cdot 2^{n-3} \\\lt 8 \cdot 2^{n-3}\\=2^n$$ where we used the three instances going from the first line to the second.
Assume that $$a_k<2^k$$ for all $$k
$$a_i=a_{i-1}+a_{i-2}+a_{i-3}\quad$$ < $$\quad2^{i-1}+2^{i-2}+2^{i-3}$$
$$RHS = 7*2^{i-3}$$ < $$8*2^{i-3}$$ = $$2^i$$