Solving a recurrence relation with the characteristic equation I have some trouble solving this due to not seeing the steps to be able to feed it into the characteristic equation.
$$T(n) = 4T(n-2) +n + 2^nn^2\ \text{with}\ \ T(0)=0,\ T(1)=1$$
(don't have to solve for the constants)
I don't understand the steps to transform this into the $(R-x)(R-y)$ form. I know that I should transform it into the $T(n) - 4T(n-2) - n - 2^nn^2 = 0$ but somewhere here I get lost. Can someone give me a hint (not solve it, from that i won't learn anything).
I know that if i look at it I like $T(n) - 4T(n-2)$ I can get it down to $(r+2)(r-2)$ which in it's turn means $T(n) = A(-2)^n + B(2)^n$. But that doesn't help me?
 A: Here is a solution
$$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}
\,.$$
First, you find $T_h(n)$ of the homogeneous recurrence relation
$$ T(n)-4T(n-2)=0 \,, $$
which you have already obtained $T_h(n)= A(-2)^n + B(2)^n  \,.$ Keep this solution aside for a while and move to the next step. The second step is to find a particular solution $T_p(n)$. See here for rules of choosing a form for the particular solution. You need to assume 
$$T_p(n) = A n + E + 2^n n(B n^2 +C n + D)$$
and substitute back in the recurrence relation
$$ T(n) = 4T(n-2) + n + 2^n n^2 \,, $$
to find the constants. The final solution is given by
$$T(n) = T_h(n) + T_p(n) = A(-2)^n + B(2)^n + T_p(n) \,.$$
Since you have given initial conditions, then you can use them to find the constants $A$ and $B$ in the above equation, once you find them, plug them back in the solution $T(n)$.  
See other techniques.
