0

If $a(n)$ is defined by: $$a(0)=1 \quad a(1)=3\quad a(2)=9 $$ and, for $n≥3$: $$a(n)=a(n-1)+2a(n-2)+5a(n-3)$$

show: $a(n) ≤ 3^n$

So I know that I'll have to use either Induction or Strong Induction to prove this statement. I'd begin by proving the base case for $3$, but I am not sure if Strong induction would apply better. I'm having trouble showing that the inequality holds. I obtained a formula that for $a(k)$ and $a(k+1)$ but it is not in in closed form. Would that help?

$$a(k+1)=98+7(a(3)+a(4)+...+a(k-2))+2a(k-1)$$

I'll try deriving a closed form for the recursion.

lulu
  • 70,402
Jawad Anwar
  • 41
  • a(n) ≤ (3^n)* there is a small typo above. – Jawad Anwar Oct 27 '16 at 19:13
  • 2
    If you were to find the closed form for the recursion, it will be of the form $a(n)=c_1 \lambda_1^n + c_2\lambda_2^n+c_3\lambda_3^n$ where $\lambda_1,\lambda_2,\lambda_3$ are the roots of the polynomial $(x^3-x^2-2x-5)$ and are approximately $2.5517, -0.77585+1.16513i, $and $-0.77585-1.16513i$ respectively and $c_1,c_2,c_3$ are appropriate constants based on the initial conditions. I think it would be easier to approach via induction using much weaker arguments than finding the exact closed form and using that approach. – JMoravitz Oct 27 '16 at 19:26
  • 1
    Note: I reformatted your question, check that I retained your meaning. I didn't understand your formula for $a(k+1)$...is that meant to be true for, say, $k=4$? Anyway, I left it as you wrote it. – lulu Oct 27 '16 at 19:26
  • 3
    Tell me... is $3^n\geq 3^{n-1}+2\cdot 3^{n-2}+5\cdot 3^{n-3}$ for large enough $n$? Maybe if we try multiplying by $3^3$ and dividing by $3^n$ this will be easier to see. Is $27\geq 9+6+5$? What does what I'm asking have to do with the original question? Why am I asking it? How do you formulate this into an inductive proof? – JMoravitz Oct 27 '16 at 19:30
  • Hmm, I saw right away that there were imaginary roots as solutions to the problem so that would be too difficult to work around. – Jawad Anwar Oct 27 '16 at 20:56
  • (Thanks for the reformat, and it's meant to be true for any values of k=3, but since I put a(k+1) it would only make sense for values of k>3). So I'm not sure how to approach the problem from that angle: how would I use your statement @JMoravitz? – Jawad Anwar Oct 27 '16 at 21:07
  • Hint: $a_n \lt a_{n-1} + 3 a_{n-2} + 9 a_{n-3}$. – dxiv Oct 27 '16 at 23:53

0 Answers0