0
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks for the help, but I'm lost. How does that line equal to 7(2^𝑘−3) < 2𝑘 ? $\endgroup$
    – Jeremy
    Commented Apr 7, 2019 at 14:21
  • $\begingroup$ $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$ $\endgroup$ Commented Apr 7, 2019 at 16:12
  • $\begingroup$ 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)$? $\endgroup$
    – Jeremy
    Commented Apr 9, 2019 at 11:58
  • $\begingroup$ I didn't write equal to! I said $\lt 7(2^{k-3})$ $\endgroup$ Commented Apr 9, 2019 at 12:41
  • $\begingroup$ It just clicked! Thanks, makes sense now. $\endgroup$
    – Jeremy
    Commented Apr 9, 2019 at 14:01
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How do you get 7⋅2𝑛−2<8⋅2𝑛−2=2𝑛+1 from that line? Thanks. $\endgroup$
    – Jeremy
    Commented Apr 8, 2019 at 11:28
  • $\begingroup$ @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. $\endgroup$ Commented Apr 8, 2019 at 15:37
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .