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. $$
Yes, there are many ways to solve this recurrence. The method that you found uses generating functions and is towards the sophisticated end. Here are three others.
(1) Guess and prove. Calculate the first few terms of the sequence:
$$\begin{array}{r|rr}n&1&2&3&4&5&6\\
T(n)&1&3&7&15&31&63
\end{array}$$
The numbers in the bottom row should look familiar: they’re one less than consecutive powers of $2$. Thus, you might at this point guess that in general $T(n)=2^n-1$. Of course, now you have to prove your guess. This typically requires a proof by induction. Getting the induction off the ground (i.e., checking the base case) is easy: $T(1)=1=2^1-1$. Now you need to show that if $T(n)=2^n-1$ is true when $n=k$, it’s also true when $n=k+1$.
Assume as your induction hypothesis that $T(k)=2^k-1$ for some $k\ge 1$. By the definition of $T$ you know that $T(k+1)=2T(k)+1$. Your induction hypothesis tells you that $T(k)=2^k-1$, so $T(k+1)=2(2^k-1)-1=2\cdot2^k-2+1=2^{k+1}-1$, which is exactly what we wanted. It follows by induction that $T(n)=2^n-1$ for all $n\ge 1$.
Added: It isn’t always so easy to guess the right formula. As Gadi A reminds me, there is a wonderful tool available to help with this, the On-Line Encyclopedia of Integer Sequences, known as OEIS. If you search it for a sequence containing $\langle 1,3,7,15,31,63\rangle$, you’ll get 29 matches, of which the first, A000225, turns out to be the right one for this problem. From the COMMENTS section of the entry:
Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e. three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one.
(2) Unwind the recurrence. Imagine that $n$ is a fairly large number, and start calculating $T(n)$ in terms of earlier and earlier terms of the sequence until you spot a pattern:
$$\begin{align*}
T(n)&=2T(n-1)+1\\
&=2\big(2T(n-2)+1\big)+1\\
&=2^2T(n-2)+2+1\\
&=2^2\big(2T(n-3)+1\big)+2+1\\
&=2^3T(n-3)+2^2+2+1\\
&\qquad\qquad\qquad\vdots\\
&=2^kT(n-k)+2^{k-1}+2^{k-2}+\dots+2+1\tag{1}\\
&=2^kT(n-k)+\sum_{i=0}^{k-1}2^k\;.\tag{2}
\end{align*}$$
Now plug $k=n-1$ into $(2)$ to get $$\begin{align*}T(n)&=2^{n-1}T(1)+\sum_{i=0}^{n-2}2^i\\
&=2^{n-1}+\big(2^{n-1}-1\big)\\
&=2^n-1\;,
\end{align*}$$
where I used the formula for the sum of a geometric series to evaluate the summation.
If you use this approach, you should then go on to prove the formula by induction, just as in the previous method, because the formula in $(1)$ was a guess $-$ a very solid guess, but still a guess requiring proof.
Another point to notice here is that the last step would have been very slightly easier if we’d backtracked the sequence by calculating $T(0)$ from $T(1)$: $T(0)=\frac12\big(T(1)-1\big)=0$. Then we could have substituted $k=n$ into $(2)$ to get the desired result directly.
(3) Turning the non-homogeneous recurrence into a homogeneous one by a change of variable. Let $S(n)=T(n)+d$ for some as yet unknown $d$. Then $T(n)=S(n)-d$, and the recurrence can be rewritten as
$$\begin{align*}
S(n)-d&=\begin{cases}2\big(S(n-1)-d\big)+1,&\text{if }n>1\\
1-d,&\text{if }n=1
\end{cases}\\\\
&=\begin{cases}
2S(n-1)-2d+1,&\text{if }n>1\\
1-d,&\text{if }n=1\;.
\end{cases}
\end{align*}$$
Move the constants to the righthand side in the recurrence: $$S(n)=2S(n-1)-d+1\;.$$ Thus, if we set $d=1$, we get rid of the constant term: $$S(n)=2S(n-1)\;.$$ This is just exponential growth: $S(n)$ doubles with each increase of $1$ in $n$. And $$S(1)=T(1)+d=1+1=2=2^1\;,$$ so it’s very easy to see that $S(n)=2^n$ for every $n\ge 1$. Finally, $T(n)=S(n)-d=2^n-1$.
For your second question, I could cook up other examples, but the Tower of Hanoi problem is by far the best known satisfying this recurrence.
Best Answer
Write $n = 2^k$ and define $U_k = T(2^k)$. The relation beocmes
$$U_k - 7\, U_{k-1} = 18 \cdot 2^{2 k}$$
with the initial condition being
$$U_1 = 1$$
I broke the equation up into a homogeneous solution and an particular solution, then applied the initial condition, as follows:
$$U_k = H_k + P_k$$
$$H_k - 7 H_{k-1} = 0 \implies H_k = A \cdot 7^k$$
Choose $P_k = B \cdot 4^k$; then
$$B \cdot 4^k - \frac{7}{4} B \cdot 4^k = 18 \cdot 4^k \implies B = -24$$
Then $U_k = A \cdot 7^k - 24 \cdot 4^k$. Use $U_1=1$ to get that
$$7 A - 96 = 1 \implies A = \frac{97}{7}$$
The result is
$$U_k =97 \cdot 7^{k-1} -96 \cdot 4^{k-1}$$
To recover $T(n)$, substitute $k=\log_2{n}$ into $U_k$. The result is
$$T(n) = \frac{97}{7} n^{\log_2{7}} - 24 n^2$$