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$

generating-functions

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?

Best Answer

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.

Related Question