4

I would like to prove the following recursively defined sequence from $n-1$ to $n$ by induction. Im not realy sure about it. Any help or alternative ways to understand and prove it are highly appreciated :

$0,1,4,12,35,98$

$a_0=0$, $a_1=1$, $a_n=a_{n-1}+5a_{n-2}+3$ for $n\geq2$

To prove $a_n\leq 3^n$

I thougt of it as: $a_{n-1}\leq 3^{n-1}$, $a_{n-2}\leq 3^{n-2}$

and thus:

$a_n\leq 3^{n-1} + 5\cdot 3^{n-2}+3$

$=3^{n-2} \cdot(3+5)+3$

$=3^{n-2} \cdot(8)+3$

$=3^{n-2} \cdot(9)+3$

$=3^{n-2} \cdot(3 \cdot 3)+3$

$=3^{n}+3$

$\leq 3^{n}$

Mamba
  • 803

1 Answers1

2

It will be easier to show $a_n \le 3^n-1$ (and hence $3^n$).

$$\begin{align} a_n &= a_{n-1} + 5a_{n-2}+3 \\ &\le (3^{n-1}-1) + 5(3^{n-2}-1) + 3 \\ &= 3^{n-1} + 5\cdot 3^{n-2} -3\\ &= 3^{n-1} + 3\cdot 3^{n-2} + 2\cdot 3^{n-2} -3\\ &= 3^{n-1} + 3^{n-1} + 2\cdot (3^{n-2} -1)-1\\ &\le 3^{n-1} + 3^{n-1} + 2\cdot 3^{n-2} - 1\\ &\le \underbrace{3^{n-1} + 3^{n-1} + 3^{n-1}}_{3^n} - 1 \end{align}$$

David P
  • 12,320