# How to solve this recurrence relation

What are some ways to solve this recurrence relation:

$a(n+1)=2 a(n) - a(n-1) -1, \text{ with }a(0)=0, a(10)=0?$

I tried to first convert this inhomogeneous equation into a homogeneous one following Wikipedia:

$b_{n}=Ab_{n-1}+Bb_{n-2}+K \,$ can be converted into homogeneous form as follows: The steady state is found by setting $b_n = b_{n−1} = b_{n−2} = b^{*}$ to obtain $b^{*} = \frac{K}{1-A-B}. \,$. Then the non-homogeneous recurrence can be rewritten in homogeneous form as $[b_n -b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}], \,$

But in the recurrence relation given at the beginning of this post, the denominator in $b^{*} = \frac{K}{1-A-B} \,$ is $1-2+1=0$. So how can I solve the recurrence relation? Thanks in advance!

PS: Are there some books or websites with some summary of various ways to solve recurrence relation?

-
Beside Andres' answer below, you can also note that $a(n+1) - a(n) = a(n) - a(n-1) - 1$. So if you let $b(n) = a(n+1) - a(n)$, you can solve for $b(n)$ by telescoping. Once you know $b(n)$ you can again solve $a(n)$ by telescoping. –  Soarer Mar 4 '11 at 7:38
Wolfram alpha provides a solution, if you need one. –  Eelvex Mar 4 '11 at 7:45

Mary: You may consider your equation for $n+2$ instead of $n+1$; this gives us $$a(n+2)=2a(n+1)-a(n)-1.$$ Subtract the first equation from this one. We obtain $$\begin{array}{rl}a(n+2)-a(n+1)&=(2a(n+1)-a(n)-1)-(2a(n)-a(n-1)-1)\\&=2a(n+1)-3a(n)+a(n-1),\end{array}$$ or $$a(n+2)=3a(n+1)-3a(n)+a(n-1).$$

In general, if your equation is "almost homogeneous" but for a constant, the same trick of subtracting consecutive instances of the recurrence gives us a homogeneous equation.

The associated characteristic equation is now $x^3-3x^2+3x-1=0$, or $(x-1)^3=0$. This means that $a(n)=A+Bn+Cn^2$ for some constants $A,B,C$.

In general, if the equation has the form $(x-r)^k(x-b)^s\dots=0$, then the general solution will have the form $$a(n)=(A+Bn+\dots+C n^{k-1})r^n+(D+En+\dots+F n^{s-1})b^n+\dots$$ (in the most studied case, the characteristic equation has no repeated roots, but as in your example here, repeated roots may occur, so we need this more general version).

To find $A,B,C$ in our equation for $a(n)=A+Bn+Cn^2$, we use the given initial conditions. Are you sure the condition $a(10)=0$ is correct, rather than $a(1)=0$?

With $a(1)=0$, we have $0=A+B+C$. Also, $a(0)=0$, so $A=0$. Finally, $a(2)=2a(1)-a(0)-1=-1$, using the original recurrence, so $A+2B+4C=-1$. This easily gives us $A=0$, $B=1/2$, and $C=-1/2$, or $$a(n)=\frac{n-n^2}2.$$

Note that we needed to compute $a(2)$ before we could find $A,B,C$. This is because the original equation was not homogeneous, so even though it is of second order, we needed an additional initial condition to the two given to us. (Note the homogeneous equation we obtained is of third order, needing 3 initial conditions.)

Unfortunately, I do not know of a decent reference on recurrence relations at an elementary level (I know of one, in Spanish, a translation of a small Russian booklet published by Mir eds. years ago). There are several standard approaches which might not be as elementary as you may want, but you may enjoy looking at them anyway: Using linear algebra or generating functions. For the latter, a good reference is "generatingfunctionology",

and for the former a good reference is Volume II of Apostol's Calculus book.

Hmm... With $a(10)=0$, we can proceed as follows: We have $$a(n)=A+Bn+Cn^2$$ and so $$A=0$$ (since $a(0)=0$) and $$10B+100C=0$$ (since $a(10)=0$ and $A=0$). We also have $$a(n+2)=2a(n+1)-a(n)-1,$$ or $$B(n+2)+C(n+2)^2=2B(n+1)+2C(n+1)^2-Bn-Cn^2-1,$$ which simplifies to $2C=-1$, or $$C=-1/2.$$ Then $$B=5,$$ from the equation for $a(10)=0$, and $$a(n)=5n-\frac{n^2}2.$$

-
Thank you! Yes I am sure it is a(10)=0, not a(1)=0. Do you have some idea then? –  Mary Mar 4 '11 at 7:49
@Mary: I edited the answer to include the case $a(10)=0$. –  Andres Caicedo Mar 4 '11 at 8:03
Thanks! In your edit, is it a coincidence that C is solvable using only the recurrence relation without using a(10)=0? I would like to know if this can be a general method or it is just for this particular problem. –  Mary Mar 4 '11 at 8:26
@Mary: I believe it is a coincidence (just as $A$ was found looking only at $a(0)$). In general, you obtain a system of linear equations ($3\times 3$ in this case), and solving it gives you the constants. It can always be solved, but not always in as easy a way as in this case. –  Andres Caicedo Mar 4 '11 at 15:55

You get all solutions of the inhomogeneous equation by finding any specific solution of the inhomogeneous equation and adding it to all solutions of the homogeneous equation. The steady-state ansatz is one way of finding a solution of the inhomogeneous equation, but if it doesn't work, as in this case, you can still pursue the general approach of first finding a specific solution to the inhomogeneous equation. Then the Wikipedia section you cited shows how to find all the homogeneous solutions that you need to add to it.

In the present case, there's also another solution: You can rewrite your recurrence relation as

$$a(n+1)-2a(n)+a(n-1)=-1\;.$$

In this form, you can see that the left-hand side is a double difference: Defining

$$(\Delta b) (n) := b (n+1) - b(n)\;,$$

we can write the equation as

$$(\Delta\Delta a)(n-1) = -1\;.$$

This we can solve by twice using the fact that "the inverse of $\Delta$ is $\Sigma$":

$$(\Delta a)(n-1) = -n + c\;,$$ $$a(n-1)= -\frac{n(n+1)}{2}+cn+d$$

with "constants of summation" $c$ and $d$ that you can determine to satisfy the initial conditions. Determining the constants will be simpler if you rewrite this as

$$a(n)=-n^2/2+c'n+d'$$

with new constants $c'$, $d'$.

-
Thanks! I was wondering if you could explain more about "the inverse of Δ is Σ"? It looks like finding antiderivative but not exactly the same. Any reference has this fact? Also what are some general approach of first finding a specific solution to the inhomogeneous equation? –  Mary Mar 4 '11 at 8:11

Generating functions to the rescue. Define $A(z) = \sum_{n \ge 0} a(n) z^n$, multiply the shifted by 2 recurrence by $z^n$ and sum over $n \ge 0$. Recognizing: \begin{align} \sum_{n \ge 0} a(n + 1) z^n &= \frac{A(z) - a(0)}{z} \\ \sum_{n \ge 0} a(n + 2) z^n &= \frac{A(z) - a(0) - a(1) z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 -z} \end{align} gives, using the unknown $a(1)$: $$\frac{A(z) - a(1) z}{z^2} = 2 \frac{A(z)}{z} - A(z) - \frac{1}{1 - z}$$ From this maxima gets the partial fraction expansion: $$A(z) = - \frac{1 + a(1)}{1 - z} + \frac{2 + a(1)}{(1 - z)^2} - \frac{1}{(1 - z)^3}$$ From here, using the generalized binomial theorem: $$a(n) = - (1 + a(1)) + (n + 1)(2 + a(1)) - \frac{(n + 1) (n + 2)}{2} = - \frac{n^2 - (2 a(1) + 1) n}{2}$$ As $a(10) = 0$, this gives $a(1) = 9 / 2$, and thus: $$a(n) = \frac{n (10 - n)}{2}$$

-