1
$\begingroup$

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figure it out :(

There are T(0) = d and T(1) = e,

Thanks in advance.

$\endgroup$
3
  • $\begingroup$ Are you given any further information about $a$ and $b$ (e.g., that they are non-negative)? $\endgroup$ – Brian M. Scott Mar 16 '13 at 19:03
  • $\begingroup$ Yes, there is an initial condition. The main question is actually for T(n) = T(n-2) + 4n, where T(0) = 2 and T(1) = 3, but I want to learn this how to do, however I could not find any suitable source to study. $\endgroup$ – icaptan Mar 16 '13 at 19:03
  • $\begingroup$ @BrianM.Scott, I think a and b are constants only, may be zero or negative. $\endgroup$ – icaptan Mar 16 '13 at 19:05
4
$\begingroup$

Your general problem is significantly harder than the specific problem that gave rise to it. I would not use the characteristic equation at all for the specific problem. For the specific recurrence $T(n)=T(n-2)+4n$ with initial conditions $T(0)=2$ and $T(1)=3$, I’d separate it into two sequences, one corresponding to even $n$ and the other to odd $n$.

Let $E(n)=T(2n)$; then $E(n)=E(n-1)+8n$, and $E(0)=2$. It follows readily that

$$E(n)=E(n-1)+8n=E(n-2)+8n+8(n-1)=\ldots E(0)+8\sum_{k=1}^nk=2+4n(n+1)$$

for all $n$. (If this is insufficiently rigorous, you can prove by induction that $E(n)=2+4n(n+1)$ for all $n$.) We can now infer that $T(2n)=E(n)=2+4n(n+1)$ for all $n$.

Let $O(n)=T(2n+1)$; then $O(n)=O(n-1)+4(2n+1)$, and $O(0)=3$, and we can make the same sort of calculation:

$$\begin{align*} O(n)&=O(n-1)+4(2n+1)\\ &=O(n-2)+4(2n-1)+4(2n+1)\\ &\;\vdots\\ &=O(0)+4\sum_{k=1}^n(2k+1)\\ &=3+8\sum_{k=1}^nk+4n\\ &=3+4n(n+1)+4n\\ &=3+4n(n+2)\;. \end{align*}$$

Again, the final result, $O(n)=3+4n(n+2)$, can be proved by induction on $n$. Combining results, we find that

$$T(n)=\begin{cases} 2+4\lfloor n/2\rfloor(\lfloor n/2\rfloor+1),&\text{if }n\text{ is even}\\\\ 3+4\lfloor n/2\rfloor(\lfloor n/2\rfloor+2),&\text{if }n\text{ is odd}\;. \end{cases}$$

Added: Suppose that you have the recurrence $T(n)=aT(n-1)+bT(n-2)+cn$, with initial values $T(0)=d$ and $T(1)=e$. The characteristic polynomial is $x^2-ax-b$. If $1$ is not a zero of the characteristic equation, there is a particular solution of the form

$$P(n)=p_0+p_1n\;;$$

if $1$ is a zero of multiplicity $m$ of the characteristic polynomial, there is a particular solution of the form

$$P(n)=n^m(p_0+p_1n)\;.$$

In your specific problem the characteristic polynomial is $x^2-1=(x-1)(x+1)$, so there is a particular solution of the form

$$P(n)=n(p_0+p_1n)\;.$$

The general solution to the homogeneous recurrence has the form $A+B(-1)^n$, so for the given initial values we must have $A+B=2$ and $A-B=3$, $A=\frac52$, and $B=-\frac12$. Thus,

$$T(n)=\frac52-\frac12(-1)^n+n(p_0+p_1n)$$

for some constants $p_0$ and $p_1$. Setting $n=1$, we see that we must have $p_0+p_1=0$, and setting $n=2$ yields the equation $10=T(2)=2+2(p_0+2p_1)$, or $4=p_0+2p_1$. Thus, $p_1=4$, $p_0=-4$, and the general solution is

$$T(n)=\frac52-\frac12(-1)^n+4n(n-1)\;.$$

More generally, if instead of $cn$ you have $k^np(n)$ for some constant $k$ and polynomial $p$ of degree $d$, there is a particular solution of the form

$$P(n)=k^n\left(p_0+p_1n+\ldots+p_dn^d\right)$$

if $k$ is not a zero of the characteristic polynomial, and there is one of the form

$$P(n)=k^nn^m\left(p_0+p_1n+\ldots+p_dn^d\right)$$

if $k$ is a zero of multiplicity $m$ of the characteristic polynomial.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. However, I did that already, the problem is to solve this with characteristic equation method. I could not solve it via ch. equation :( $\endgroup$ – icaptan Mar 16 '13 at 19:27
  • $\begingroup$ @icaptan: I’ve added a solution using the characteristic polynomial and a particular solution. $\endgroup$ – Brian M. Scott Mar 16 '13 at 20:11
  • $\begingroup$ M. Scoot thanks for the answer. There two answers here, but I could not use both. My reputation is not enough to vote down. Currently I try to get the idea. Thanks again ! $\endgroup$ – icaptan Mar 16 '13 at 20:23
  • $\begingroup$ @icaptan: You’re welcome! Feel free to ask if you have any questions about the part that I added. $\endgroup$ – Brian M. Scott Mar 16 '13 at 20:24
  • 1
    $\begingroup$ @icaptan: Yes, $A(1)^n+B(-1)^n$ comes from the roots $1$ and $-1$ of $x^2-1=(x-1)(x+1)$, and yes, I used $T(0)$ and $T(1)$ to get $A$ and $B$. The $n$ in $n(p_0+p_1n)$ comes from the fact that $1$ is a zero of $x^2-1$ of multiplicity $1$; in other words, $m=1$ here. The $p_0+p_1n$ comes from the fact that the forcing term $cn$ is a first-degree polynomial, so the particular solution will be a first-degree polynomial (multiplied by a power of $n$ if $1$ is a zero of the characteristic polynomial, as it is here). Then I used $T(1)$ and $T(2)$ to calculate $p_0$ and $p_1$. $\endgroup$ – Brian M. Scott Mar 16 '13 at 21:48
2
$\begingroup$

We use your specific equation. Look for a particular solution of the shape $an^2+bn+c$, actually in this case $an^2+bn$ is good enough.

Substituting in the equation, we get $an^2+bn=a(n-2)^2+b(n-2)+4n$, Comparing coefficients, we find that $-4a+4=0$ and $4a-2b=0$. Thus $a=1$, $b=2$. So we have found the particular solution $n^2+2n$.

Now let $T(n)=S(n)+n^2+2n$. Then we find that $S(n)$ satisfies the homogeneous equation $S(n)=S(n-2)$. The method of characteristic equations shows that the general solution of the homogeneous equation is $A(1^n)+B(-1)^n$. Use our initial conditions to determine $A$ and $B$.

Similar ideas will work for, say, $T(n)=pT(n-1)+qT(n-2)+P(n)$, where $p$ and $q$ are constants, and $P(n)$ is a polynomial.

$\endgroup$
5
  • $\begingroup$ thanks for the answer, currently i try to figüre out $\endgroup$ – icaptan Mar 16 '13 at 20:05
  • $\begingroup$ You are welcome. Please note there was a horrible typo, I meant let $T(n)=2n^2+4n+S(n)$. $\endgroup$ – André Nicolas Mar 16 '13 at 20:10
  • $\begingroup$ Thanks, but I could not get how S(n) = S(n-2), it is S(n) = T(n-2) right ? $\endgroup$ – icaptan Mar 16 '13 at 20:24
  • $\begingroup$ You are right, I made a mistake setting up the linear equations. should not try to do several things at once. Edited. We have $a=1$ and $b=2$. Now it will work. Once we have found a particular solution, it always has to work, for general linear algebra reasons. $\endgroup$ – André Nicolas Mar 16 '13 at 20:54
  • $\begingroup$ nope, I could not use your idea, too. I know my knowledge is not well enough to do it :/ $\endgroup$ – icaptan Mar 16 '13 at 21:41

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.