5
$\begingroup$

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?

  • 0
    Sorry for not realizing this site understands LaTeX formatting! Thanks for edit :)2012-10-09

1 Answers 1

4

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.

  • 0
    @saxly: This the solution to the homogeneous recurrence. call it $T_h(n) = A(-2)^n + B(2)^n$ and just keep it aside for the moment. Now, find the particular solution as I mentioned in my answer $T_p(n)$. So you have to find all the constants. Once you do that, write the general soltion $T(n)= A(-2)^n + B(2)^n + T_p(n)$ and use the initial conditions to find $A$ and $B$.2012-10-09