0

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?

user136457
  • 2,560
  • 1
  • 22
  • 41

2 Answers2

1

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.

TZakrevskiy
  • 22,980
  • Thank you for your answer. I have indeed seen this approach. But as third order recurrence equations are much nastier to solve than second order, I hoped for another solution that does not need to lift the order. – user136457 Nov 07 '14 at 20:41
  • @user136457 see edit, I remembered another trick. – TZakrevskiy Nov 07 '14 at 21:22
  • Thank you for the other trick. Seems to be quite useful for lot of problems. But I also have to solve some problems where $1+a+b=0$. – user136457 Nov 08 '14 at 05:41
  • @user136457 see another edit. – TZakrevskiy Nov 08 '14 at 13:34
  • Thank you for your second edit. I am not sure: do you mean when $a \neq -1$ there instead of $a \neq 1$? Moreover, why is the recurrence trivial when $a=-1$, so we only have $T(n+1) - T(n) + b T(n-1) + c = 0$. Why is this easier to solve than other recurrences? – user136457 Nov 08 '14 at 14:18
  • @user136457 in the second edit I suppose everywhere that $1+a+b=0$, so the condition $a=-1$ transforms the relation into $T(n+1)=T(n)-c$ (i.e. it becomes of the first order). – TZakrevskiy Nov 08 '14 at 14:23
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.

user72272
  • 168
  • 1
  • 10