Turning a closed-form generating function back to ordinary power series

Question

If I know the formal power series, I know how to find the closed form:

$$\displaystyle F = \sum_{n=0}^{\infty} {X^n} = 1 + X^1 + X^2 + X^3 + ...$$

$$\displaystyle F \cdot X = X \cdot \sum_{n=0}^{\infty} {X^n} = X^1 + X^2 + X^3 + X^4 + ...$$

$$\displaystyle F - F \cdot X = 1 $$ $$\displaystyle F = \frac 1 {1 - X} $$

But if I only know the closed form $\frac 1 {1 - X}$, how do I turn it back into the series $1 + X^1 + ...$? In other words, how do I do extract the coefficients if I only know the closed form and I do not know that $\frac 1 {1 - X}$ corresponds to $1 + X^1 + ...$.

My textbook and everywhere I looked at seems to avoid talking about this, and somehow magically transform things back and forth with a set of known formulas. Is there a better way to do this, or is formula matching the best we can do?

Edit: This is the type of questions I need to solve:

Find the coefficient of $X^8$ in the formal power series $(1 - 3X^4)^{-6}$

Answer 1

The quickest way to transform your generating function to a power series is to have a table of formulae handy. For a given rational function, you would use partial fraction expansion if necessary and switch back to the power series by looking at the appropriate entry in the table for each term. If you look at Herbert Wilf's book http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf , in section 2.5, he has a list of such formulae.

You have

\begin{equation} \frac{1}{(1-x)^{k+1}} = \sum_n \binom{n+k}{n} x^n \end{equation}

So, for your case, we have

\begin{equation} \frac{1}{(1-3x^4)^6} = \sum_n \binom{n+5}{n} 3^n x^{4n} \end{equation}

The coefficient of $x^8$ in this expansion is $3^2 \times \binom{7}{2} = 189$.

It is actually not difficult to derive the identity. You start with

\begin{equation} \frac{1}{1-x} = 1+x+x^2 +\ldots \end{equation}

Take derivative on both sides k times and you will get

\begin{equation} \frac{k!}{(1-x)^{k+1}} = \sum_n [(n+k)(n+k-1) \ldots n]x^n \end{equation}

this simplifies to

\begin{equation} \frac{1}{(1-x)^{k+1}} = \sum_n \binom{n+k}{n} x^n \end{equation}

Answer 2

Differentiation $n$ times, setting the variable to 0, multiplying by $n!$ gets you the $n$th coefficient of the ogf of a function $f$. That is, if $F(x)$ is the ogf of $f(n)$ then

$$f(n) = [(D^nf)(0)]\cdot n!$$.

But you want the closed form of $f$ from the ogf. For the most part, that is an ad hoc process (svenkatr's answer gives a particular method for $\frac{1}{(1-x)^k}$).

A general method is to use the above differentiation trick (essentially computing the Taylor series), but finding a pattern from it. For a simple example, if $F(x)= \log \frac{1}{1-x}$, differentiating numerous times, you'll see the pattern 1, 1/2, 1/3, 1/4,..., so you'll notice and be able to prove) that $f(n) = 1/n$.