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.
Best Answer
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.