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?
 A: 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", 

http://www.math.upenn.edu/~wilf/DownldGF.html 

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. $$
A: 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'$.
A: 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}
$$
