# Solving a recurrence by using characteristic equation method

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,

• Are you given any further information about $a$ and $b$ (e.g., that they are non-negative)? – Brian M. Scott Mar 16 '13 at 19:03
• 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. – icaptan Mar 16 '13 at 19:03
• @BrianM.Scott, I think a and b are constants only, may be zero or negative. – icaptan Mar 16 '13 at 19:05

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.

• 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 :( – icaptan Mar 16 '13 at 19:27
• @icaptan: I’ve added a solution using the characteristic polynomial and a particular solution. – Brian M. Scott Mar 16 '13 at 20:11
• 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 ! – icaptan Mar 16 '13 at 20:23
• @icaptan: You’re welcome! Feel free to ask if you have any questions about the part that I added. – Brian M. Scott Mar 16 '13 at 20:24
• @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$. – Brian M. Scott Mar 16 '13 at 21:48

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.

• thanks for the answer, currently i try to figüre out – icaptan Mar 16 '13 at 20:05
• You are welcome. Please note there was a horrible typo, I meant let $T(n)=2n^2+4n+S(n)$. – André Nicolas Mar 16 '13 at 20:10
• Thanks, but I could not get how S(n) = S(n-2), it is S(n) = T(n-2) right ? – icaptan Mar 16 '13 at 20:24
• 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. – André Nicolas Mar 16 '13 at 20:54
• nope, I could not use your idea, too. I know my knowledge is not well enough to do it :/ – icaptan Mar 16 '13 at 21:41