Solving easy inhomogeneous second order recurrence equations

Question

I know the method of solving the characteristic equation to solve homogeneous second order recurrence equations.

Now there is added an inhomogeneous term $c$, a constant.

I have seen many different approaches to handle such summands, but mainly when $c=2^n$ or something like this.

So is there an easy way to solve

$T(n+1)+aT(n)+bT(n-1) +c=0$, where $a,b,c$ are constants?

Answer 1

Since you have a linear recurrence equation, perhaps another way might be to use the $\mathcal{Z}$-transform first and then solve for $T(z)$ and use inverse $\mathcal{Z}$-transform to get $T(n)$. The $\mathcal{Z}$-transform of the recurrence equation you wrote above is $$\mathcal{Z}\left[T(n+1)+aT(n)+bT(n-1)+c\right]=0\\zT(z)-zT(0)+aT(z)+bz^{-1}T(z)+c\frac{1}{1-z^{-1}}=0\\T(z)=\frac{\left(T(0)z-T(0)+c\right)z^2}{(z-1)(z^2+az+b)}$$ which can be rewritten using partial fractions as $$T(z)=a_1\frac{z}{z-1}+a_2\frac{z}{z+\frac{a+\sqrt{a^2-4b}}{2}}+a_3\frac{z}{z+\frac{a-\sqrt{a^2-4b}}{2}}$$ where $a_1$, $a_2$, and $a_3$ are $$a_1=\frac{c}{a+b+1},\quad a_2=\frac{\left(-T(0)\frac{a+\sqrt{a^2-4b}}{2}-T(0)+c\right)\left(\frac{a+\sqrt{a^2-4b}}{2}\right)^2}{\left(-\frac{a+\sqrt{a^2-4b}}{2}-1\right)\left(-\sqrt{a^2-4b}\right)},\quad a_3=\frac{\left(T(0)\frac{-a+\sqrt{a^2-4b}}{2}-T(0)+c\right)\left(\frac{a-\sqrt{a^2-4b}}{2}\right)^2}{\left(\frac{-a+\sqrt{a^2-4b}}{2}-1\right)\left(\sqrt{a^2-4b}\right)}$$ which can be transformed back to $n$-domain using $\mathcal{Z}$-transform as $$T(n)=a_1+a_2\left(\frac{-a-\sqrt{a^2-4b}}{2}\right)^n+a_3\left(\frac{-a+\sqrt{a^2-4b}}{2}\right)^n.$$ Here, I assumed that $a^2-4b\geq0$ to obtain real roots of the term, $z^2+az+b$ in the denominator of $T(z)$. If $a^2-4b<0$, then you have complex conjugate roots and the situation is a bit more involved however it is still solvable. See these notes http://staff.neu.edu.tr/~fahri/signals_10.pdf for example.

Answer 2

Take your recurrence relation for $T(n+2)$ and subtract from it the recurrence relation for $T(n+1)$.

You obtain a higher order recurrence relation, but now it is homogenuous.

Edit

Completely forgot about this useful trick: if $d=1+a+b\ne 0$, then the sequence $T'(n):=T(n)+\frac cd $ satisfies the relation

$$T'(n+1)+aT'(n)+bT'(n-1)=0.$$ In other words, if $1$ is not a root of the characteristic polynomial.

Edit 2 The case $1+a+b=0$ is more difficult. If $a=-1$, then the recurrence relation becomes quite trivial. If $a\ne 1$, then we can fall back to a standard method: let $$A = \begin{pmatrix}-a&a+1\\1&0\end{pmatrix},\quad u(n+1) =\begin{pmatrix}T(n+1)\\T(n)\end{pmatrix} ,\quad C= \begin{pmatrix}c\\0\end{pmatrix}.$$ Then the relation becomes $$u(n+1)=Au(n)+C,$$ which is easy to solve:

$$u(n) =A^n D+\sum_{k=0}^n A^{n-k}C, $$ where $D$ is a constant vector found from initial data.