Calculating and proving the generating function for the recursion $a_n = 2a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$? I'm trying to calculate the generating function for the recursion $a_n = 2a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$. I've found all sorts of related facts, like the OEIS series of the coefficients (A001333), or the actual equation $a_n = \frac{(1-\sqrt2)^n + (1+\sqrt2)^n}2$, but I can't find the generating function. How would I do this, and what's the answer?
EDIT: So now I know the answer is $\frac{1-x}{1 - 2x - x^2}$. But how would I prove that?
 A: The OEIS itself has this line in the formula section of A001333:
G.f.: (1 - x) / (1 - 2*x - x^2) = 1 / (1 - x / (1 - 2*x / (1 + x))). - Michael Somos, Sep 02 2012

"G.f." indicates a generating function in the OEIS, so you are looking for $\frac{1-x}{1-2x-x^2}$. Similarly, "E.g.f" indicates an exponential generating function.
A: Here is one way to derive the generating function.
It's important to note the range of $n$ for which the recursion holds:
$$a_n= 2a_{n-1}  +a_{n-2}$$
for $\color{red}{n \ge 2}$, with $a_0=1$ and $a_1=3$.
We can use the initial conditions and the Kronecker delta function to rewrite the recursion in a form that holds for all $n \ge 0$:
$$a_n= 2a_{n-1}  +a_{n-2} + \delta_{0n} +\delta_{1n}$$
(You should study this equation to see how it works.)
Now multiply by $x^n$
$$a_n x^n = 2a_{n-1} x^n +a_{n-2} x^n + \delta_{0n} x^n +\delta_{1n} x^n$$
and sum over $n$, with the result
$$\sum_{n=0}^{\infty} a_n x^n = \sum_{n=0}^{\infty} 2a_{n-1} x^n +\sum_{n=0}^{\infty} a_{n-2} x^n + 1 + x$$
If we define $$f(x) = \sum_{n=0}^{\infty} a_n x^n$$
then the previous equation becomes
$$f(x) = 2x f(x) + x^2 f(x) +1 +x$$
which you can now solve for $f(x)$, with the result
$$f(x) = \frac{1+x}{1-2x-x^2}$$
