Búsqueda de $a_n$ grandes $n$ donde $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $

Question

Tengo una relación de recurrencia,

$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ para $n>3$ $a_1 = 0, a_2 = 0, a_3 = 1$

Tengo que encontrar el valor de $a_n$ para valores muy grandes de n. He intentado un enfoque similar a la que utilizamos para la búsqueda de los números de fibonacci utilizando el método de la matriz que nos da $f_n$ $log(n)$ tiempo de complejidad. Pero no estoy en condiciones de uso aquí porque de la $2^{n-3}$ plazo.

Podemos hacer mejor que $O(n)$ tiempo de complejidad.

Answer 1

Para $n \in \mathbb N$, dejamos $b_n = a_n - 2^n$. Se obtiene haciendo uso de la ecuación de $(a_n)$: \begin{align*} b_n &= a_n - 2^n\\ &= a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} - 2^n\\ &= b_{n-1} + 2^{n-1} + b_{n-2} + 2^{n-2} + b_{n-3} + 2^{n-3} + 2^{n-3} - 2^n\\ &= b_{n-1} + b_{n-2} + b_{n-3} + 2^{n-3}\cdot(4 + 2 + 1 + 1 - 8)\\ &= b_{n-1} + b_{n-2} + b_{n-3}, \end{align*} con los valores iniciales $b_1 = -2$, $b_2 = -4$, $b_3 = -7$.

Así, por $(b_n)$ nos hemos librado de la $2^{n-3}$-plazo y pueden usar el mismo truco como de los números de Fibonacci.