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?

  • $\begingroup$ Sorry for not realizing this site understands LaTeX formatting! Thanks for edit :) $\endgroup$ – saxly Oct 9 '12 at 5:10

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.

  • 2
    $\begingroup$ The op specifically asked for the problem not to be solved but rather a hint. $\endgroup$ – EuYu Oct 9 '12 at 4:48
  • $\begingroup$ @EuYu: I just gave the final solution and see the edit. $\endgroup$ – Mhenni Benghorbal Oct 9 '12 at 4:51
  • $\begingroup$ So if i the recurrence relation of $T(n) - 4T(n-2)$ is $T(n) = A(-2)^n + B(2)^n$ it means that the ah... I just don't get it. By specifying that i shall not solve for the constants i only have to figure out the recurrence relation right? Why are they even there to begin with... $\endgroup$ – saxly Oct 9 '12 at 5:09
  • $\begingroup$ @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$. $\endgroup$ – Mhenni Benghorbal Oct 9 '12 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.