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$
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$
  • $\begingroup$ Thanks for the help, but I'm lost. How does that line equal to 7(2^𝑘−3) < 2𝑘 ? $\endgroup$ – Jeremy Apr 7 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$ – Peter Foreman Apr 7 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 Apr 9 at 11:58
  • $\begingroup$ I didn't write equal to! I said $\lt 7(2^{k-3})$ $\endgroup$ – Peter Foreman Apr 9 at 12:41
  • $\begingroup$ It just clicked! Thanks, makes sense now. $\endgroup$ – Jeremy Apr 9 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$
  • $\begingroup$ How do you get 7⋅2𝑛−2<8⋅2𝑛−2=2𝑛+1 from that line? Thanks. $\endgroup$ – Jeremy Apr 8 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$ – Shubham Johri Apr 8 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.