Solving simple linear recurrences with generating functions

I know how to solve sequences like the Fibonacci using generating functions, but how do you solve recurrences when there is a constant? A simple example would be $a_{n+1}=2a_{n}-1, a_0=0$. The generating function of this would be result in $\frac{1}{(1-x)^2}$, which just yields solutions in the form $A(1)^n$ for a constant $A$, which is obviously false. Why does this generating function method not work when there are constants involved? What is the best way to solve such recurrences? Thanks.

Solution 1:

Problems of this type, say $a_n=Aa_{n-1}+B$, which I call a short Fibonacci sequence, can be converted to a generalize Fibonacci form, i.e., $f_n=af_{n-1}+bf_{n-2}$, as follows

$$a_n=Aa_{n-1}+B\\ a_{n-1}=Aa_{n-2}+B$$

so that eliminating $B$ we get

$$a_n=(A-1)a_{n-1}-Aa_{n-2}$$

From here you should be able to get the generating function in the usual way. I use a different method, so you should be able to compare your results with mine. Going through a formal derivation of the generalized Fibonacci sequence, as described here, we can show that

$$a_n=\frac{[(A-1)a_0+B]A^n-B}{A-1}$$

This gives us a solution, once and for all such short Fibonacci sequences. In the present case, we have $A=2,~B=-1$, so that

$$T_n=[a_0-1]2^n+1$$

I have verified these results numerically.