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$?

Question

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?

Answer 1

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.

Answer 2

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}$$