Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$

share|improve this question
    
taylor series, start differentiating! –  yoyo Mar 12 '11 at 16:17
    
@yoyo: can you elaborate on that? –  Lie Ryan Mar 12 '11 at 16:43
    
For rational functions, the easiest way to find a power series is probably to use long division. Rewrite $a/b$ as $(a-cb)/b + c$, where $c$ is the quotient of the lowest-degree terms of $a$ and $b$. Repeat ad nauseam. –  Tanner Swett Jun 3 at 2:00

2 Answers 2

up vote 7 down vote accepted

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}

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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