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." 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.