Textbook questions on generating functions I'm doing math by doing practice problems in my textbook.
I was able to find the explicit formula for $a_n$ such that $a_{n+1}=a_n+2^n$ (which is $2^k-1$) I understand the theorems, but I'm having trouble solving questions.
I'm stuck on the second problem already.  How do I find the explicit formula for the sequence $a_n$ that's defined by recurrence relation $a_{n+2}=a_{n+1}+2a_n$ and $a_0=a_1=1$?  First of all, how do I even find a generating function?
 A: Say we have a generating function $g(x) = \displaystyle \sum_{n=0}^\infty a_n x^n$ for $a_n$.
Then $g(x) = \displaystyle 1 + x + \sum_{n=2}^\infty (a_{n-1} + 2a_{n-2})x^n = 1 + x + \sum_{n=2}^\infty a_{n-1}x^n + 2\sum_{n=2}^\infty a_{n-2}x^n$
But we have that $\displaystyle \sum_{n=2}^\infty a_{n-1}x^n = x \sum_{n=2}^\infty a_{n-1} x^{n-1} = x(g(x) - 1)$, and similarly, $\displaystyle \sum_{n=2}^\infty a_{n-2}x^n = x^2 \sum_{n=2}^\infty a_{n-2}x^{n-2} = x^2g(x)$.
That means that $g(x) = 1 + x + x(g(x) - 1) + 2x^2g(x)$. From there you can solve for the generating function and work on extracting the coefficients.
A: Let $F(x)$ be $\sum_{n=0}^{\infty}a_nx^n$, the generating function.
To find the $F(x)$, rephrase the recurrence relation of the terms into an equation involving the generating function, like this:
$$a_{n+2} = a_{n+1} + 2a_n$$
$$\sum_{n=0}^{\infty}a_{n+2}x^n = \sum_{n=0}^{\infty}a_{n+1}x^n + 2\sum_{n=0}^{\infty}a_nx^n$$
Now, since, for example, $\sum_{n=0}^{\infty}a_{n+1}x^n = \frac{F(x)-a_0}{x}$, we can write that as
$$\frac{F(x)-a_0-a_1x}{x^2} = \frac{F(x)-a_0}{x} + 2F(x),$$
which, after a bit of algebra, can be solved for $F(x)$.
To find the explicit formula, you can take the rational function you get for $F(x)$, and expand it into a power series using partial fractions. The resulting formula may be quite messy, and involve roots of polynomials in the generating function.
