0

If $a_0=1$， $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$.

I don't know how to type it in right format. $n+3$ and such things in the parentheses are small and in the lower right corner.

I think this question relates to recursion and induction, but I cannot solve it.

ForgotALot
  • 3,931
Nie
  • 1

2 Answers2

1

This looks suitable for induction.

First you have to prove a base case, in this it would be for $n=0$, and the statement to prove is $a_0\leq 3^0$. That's shouldn't be a problem.

Then you have to do the inductive step, i.e. prove that if $a_k\leq 3^k$ for $k\leq n$ then $a_{n+1}\leq 3^{n+1}$.

If we rewrite the recursive defintion, to get $a_{n+1}$, we get: $$ a_{n+1}=a_n+4a_{n-1}+5a_{n-2} $$ If you use the inductive hypothesis you get

(I won't give you that)

At this point you have to use that $5+3<9$, but then it follows quite simply.

Henrik supports the community
  • 6,831
0

This is strong induction.

The case for $a_0$ and $a_1$ and $a_2$ are givens.

Suppose true for all $a_n$ $n \le k$ for some k.

Then $a_{k+1} = a_k + 4a_{k-1} + 5a_{k-2} \le 3^k + 4*3^{k-1} + 5*3^{k-2}$

$= 3^k + (3 + 1)*3^{k_1} + (3 + 2)3^{k-2} = $

$3^k + 3^k + 3^{k-1} + 3^{k-1} + 2*3^{k-2} =$

$2*3^k + 2*3^{k-1} + 2*3^{k-2} = $

$2*3^k + (3 - 1)3^{k-1} + (3-1)3^{k-2}= $

$2*3^k + 3^k -3^{k-1} + 3^{k-1} - 3^{k-2} =$

$3^k - 3^{k-2} < 3^k$.

fleablood
  • 124,253