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

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.

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.

• Thanks for the help, but I'm lost. How does that line equal to 7(2^𝑘−3) < 2𝑘 ? – Jeremy Apr 7 at 14:21
• $2^{k-1}=4(2^{k-3})$ and $2^{k-2}=2(2^{k-3})$ and then $7(2^{k-3})\lt8(2^{k-3})=2^k$ – Peter Foreman Apr 7 at 16:12
• But in the case $k = 5, a_k = 3 + 7 + 11 = 21$, and $2^k-3 = 4$, so $7(2^k-3) = 28$, so surely $a_k$ doesn't = $7(2^k-3)$? – Jeremy Apr 9 at 11:58
• I didn't write equal to! I said $\lt 7(2^{k-3})$ – Peter Foreman Apr 9 at 12:41
• It just clicked! Thanks, makes sense now. – Jeremy Apr 9 at 14:01

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.

• How do you get 7⋅2𝑛−2<8⋅2𝑛−2=2𝑛+1 from that line? Thanks. – Jeremy Apr 8 at 11:28
• @Jeremy $2^n=4\times2^{n-2},2^{n-1}=2\times2^{n-2}.7$ times a positive quantity is always going to be smaller than $8$ times the same quantity. – Shubham Johri Apr 8 at 15:37

$$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<...$$