Use geometric progression formula to expand generating function into a power series?

Question

I am a software engineer and I am studying combinatorics on my own to enhance my learning. I have been finally starting to get the hang of generating functions, but the following problem below has me stumped.

Problem

Use geometric progression to expand $G(x)$ into a power series. Collect terms with $x^n$. Please note that the coefficient at $x^n$ will give you the formula for $a_n$. Please note that I have demonstrated on my own that $G(x) = \frac{1+x}{(1+2x)(1-x)}$ where $a_n = (-2a_{n-1} + 2)$ and $a_0 = 1$.

Attempt

I have proven previously on my own that $G(x) = \frac{1+x}{(1+2x)(1-x)}$. Therefore, it follows by hand that $G(x) = 1 + 0x + 2x^2 -2x^3 -6x^4 + ...$

Here is the rub, so to speak. I believe the above suffices in that it is a power series. However, I doubt that I have collected the terms at $x^n$ and given myself the formula for $a_n$. That is, a way to express this as a sum with a formula to produce the coefficient at $x^n$. If possible, could someone please help me to do this? Is there an algorithmic way to solve for this once you get the power series expanded or are there some math manipulation identities that I am ignorant of that help?

Again, I doubt I solved the problem as it was intended. As I stated before, I am a software developer and not a mathematician, so I deeply appreciate any elaboration and assistance.

Answer 1

Let's split up $G(x)$ into partial fractions: $$G(x) = \frac{1+x}{(1+2x)(1-x)}=\frac{A}{1+2x}+\frac{B}{1-x}=\frac{A-Ax+B+2Bx}{(1+2x)(1-x)}=\frac{A+B+(2B-A)x}{(1+2x)(1-x)}$$

We obtain the equations $A+B=1$ and $2B-A=1$, with solution $A=1/3, B=2/3$. Hence $$G(x) = \frac{1/3}{1+2x}+\frac{2/3}{1-x}=\frac{1/3}{1-(-2x)}+\frac{2/3}{1-x}=\frac{1}{3}\sum_{n=0}^\infty (-2x)^n + \frac{2}{3}\sum_{n=0}^\infty x^n=\sum_{n=0}^\infty \Big(\frac{1}{3}(-2)^n+\frac{2}{3}\Big)x^n$$

Now we see that the coefficients are $a_n=\frac{(-2)^n+2}{3}$. As a quick sanity-check, note that indeed $a_0=\frac{(-2)^0+2}{3}=\frac{3}{3}=1$.

The point is, you can use partial fractions to (hopefully) split your generating function into a sum of geometric series, each being very easy to handle. In other words, its a divide-and-conquer approach!