1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can see two ways to proceed: either by partial fractions or by interpreting $\frac{1}{1-x}$ as the summation operator and go from there. I assume partial fractions is what you're after? $\endgroup$ – A.Sh Dec 14 '15 at 16:31
3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thank you for your concise and minimalist answer. I wish I could give more than one point for this well laid out and helpful answer. It was more educational than the book I am reading. :) $\endgroup$ – hlyates Dec 14 '15 at 22:10
  • $\begingroup$ Glad to be of help again :) (Btw, which book are you reading? Just curious…) $\endgroup$ – A.Sh Dec 14 '15 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.