Resolver una relación de recurrencia con la ecuación característica

Question

Tengo algunos problemas para resolver esto debido a que no veo los pasos para poder introducirlo en la ecuación característica.

$$T(n) = 4T(n-2) +n + 2^nn^2\ \text{with}\ \ T(0)=0,\ T(1)=1$$ (no hay que resolver las constantes)

No entiendo los pasos para transformar esto en el $(R-x)(R-y)$ forma. Sé que debo transformarlo en el $T(n) - 4T(n-2) - n - 2^nn^2 = 0$ pero aquí me pierdo. Puede alguien darme una pista (no resolverlo, de eso no aprenderé nada).

Sé que si lo miro me gusta $T(n) - 4T(n-2)$ Puedo bajarlo a $(r+2)(r-2)$ que a su vez significa $T(n) = A(-2)^n + B(2)^n$ . ¿Pero eso no me ayuda?

Answer 1

He aquí una solución

$$T(n) = \frac{1}{2}\,{2}^{n}+{\frac {7}{18}}\, \left( -2 \right)^{n}-{\frac {8}{9}}-\frac{n}{3}+ \left( n+1 \right) \left( \frac{n}{2}+1 \right) \left( \frac{n}{3}+1 \right) {2}^{n}$$ $$- \left( n+1 \right) \left( \frac{n}{2}+1 \right){2}^{n} \,.$$

En primer lugar, usted encontrar $T_h(n)$ de la relación de recurrencia homogénea $$ T(n)-4T(n-2)=0 \,, $$ que ya ha obtenido $T_h(n)= A(-2)^n + B(2)^n \,.$ Deja esta solución a un lado durante un tiempo y pasa al siguiente paso. El segundo paso es encontrar una solución particular $T_p(n)$ . Ver aquí para las reglas de elección de una forma para la solución particular. Es necesario asumir $$T_p(n) = A n + E + 2^n n(B n^2 +C n + D)$$ y volver a sustituir en la relación de recurrencia $$ T(n) = 4T(n-2) + n + 2^n n^2 \,, $$ para encontrar las constantes. La solución final viene dada por $$T(n) = T_h(n) + T_p(n) = A(-2)^n + B(2)^n + T_p(n) \,.$$ Como has dado las condiciones iniciales, entonces puedes usarlas para encontrar las constantes $A$ y $B$ en la ecuación anterior, una vez que los encuentres, introdúcelos en la solución $T(n)$ .

Ver otras técnicas .