0
$\begingroup$

I am trying to answer the following question:

Define a recurrence relation by $a_0=a_1=a_2=2$ and $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ for $n\ge3$. Prove by induction: $a_n\le 2^n$ for all $n\ge1$.

Is it true that \begin{align} a_4 & = a_3+a_2+a_1\\ & =(a_2+a_1+a_0)+a_2+a_1\\ & = a_0+2a_1+2a_2\\ & = 2+4+4\\ & = 10? \end{align}

But by our result $a_4<8$, but this does not hold for $10<8$.

Could it be possible that $a_n<2^n$ for all $n>1$ is not true. Looking for clarification on this problem?

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to MSE. For tips on how to format etd see tutorial. You will get a better response if it is properly formatted. $\endgroup$ – almagest Sep 25 '19 at 16:05
  • $\begingroup$ It should be $$10 = a_4 < 2^4 = 16$$so it's true. $\endgroup$ – Max Wong Sep 25 '19 at 16:06
  • 1
    $\begingroup$ Also people here hate images when not strictly necessary. Please include question directly. I have just done it for you this time. $\endgroup$ – almagest Sep 25 '19 at 16:14
0
$\begingroup$

$a_3 = 2 +2 +2 = 6$, $a_4 = 6 + 2 +2 = 10$, and $2^4 = 16$, so the hypothesis holds.

To prove the hypothesis by induction, we have already proven it until $n=4$. Now, assume it holds for $n=1,..N$ and we want to prove it for $N+1$. Then:

\begin{align*} a_{N+1} &= a_N + a_{N-1} + a_{N-2}\\ &<2^N +2^ {N-1} +2^{N-2}\\ & = 2^2\times 2^{N-2} + 2 \times 2^{N-2} + 2^{N-2}\\ & = 7 \times 2^{N-2}\\ & < 8 \times 2^{N-2}\\ & = 2^{N+1} \end{align*}

Where the second line comes from the induction hypothesis.

$\endgroup$

Your Answer

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