Prove by strong induction that $a_n < 2^n$ for all integers $n ≥ 1$, given a list of $a_n$ values.

Question

Let $a_1, a_2, a_3, . . .$ 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$.

I understand how induction works, but I'm not sure how you structure using strong induction, or why it's really needed. Thanks for any help.

Answer 1

Assume that for some $k\in\mathbb{N}$ we have $$a_{k-3}\lt2^{k-3}$$ $$a_{k-2}\lt2^{k-2}$$ $$a_{k-1}\lt2^{k-1}$$ Then the induction step would be to find $a_k$ $$a_k=a_{k-1}+a_{k-2}+a_{k-3}\lt2^{k-1}+2^{k-2}+2^{k-3}=7(2^{k-3})\lt2^k$$ So as $$a_k\lt2^k$$ we can just take $k=4$ and thus the conjecture is true.

Answer 2

For the base step, note that $a_1<2,a_2<2^2,a_3<2^3,a_4<2^4$. Assume that $a_k<2^k~\forall k\le n$. Then,$$a_{n+1}=a_n+a_{n-1}+a_{n-2}<2^n+2^{n-1}+2^{n-2}=7\cdot2^{n-2}<8\cdot2^{n-2}=2^{n+1}$$Note that it is sufficient to assume that $a_k<2^k$ for $k=n,n-1,n-2$ in the inductive hypothesis.

Answer 3

$a_1<2^0, a_2<2^2$ and $a_3<2^3$

Now suppose for $n>3$ both $a_{n-3}<2^{n-3}$, $a_{n-2}<2^{n-2}$ and ${a_{n-1}}<2^{n-1}$, add them to find that $a_n<...$