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 figüre it out 🙁

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

Thanks in advance.

Solutions Collecting From Web of "Solving a recurrence by using characteristic equation method"

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.

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.