demostrando de forma recursiva secuencia definida por inducción

Question

Me gustaría probar la siguiente forma recursiva definida por la secuencia de $n-1$ $n$por inducción. No estoy realmente seguro de ello. Cualquier ayuda o formas alternativas de entender y demostrar que son muy apreciados :

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

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

Para demostrar $a_n\leq 3^n$

Yo thougt de como: $a_{n-1}\leq 3^{n-1}$, $a_{n-2}\leq 3^{n-2}$

y por lo tanto:

$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}$

Answer 1

Será más fácil para mostrar $a_n \le 3^n-1$ (y, por tanto,$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}$$