# Partial fraction of $\frac{x^n}{(1-x)(1-2x)(1-3x)\ldots(1-nx)}$

How should you break $\displaystyle \frac{x^n}{(1-x)(1-2x)(1-3x)\ldots(1-nx)}$ into partial fractions?

-

First you have to take out a multiple of the denominator to make the degree of the numerator smaller than that of the denominator:

$$\frac{x^n}{(1-x)(1-2x)(1-3x)\ldots(1-nx)}$$

$$= \frac{(-1)^n}{n!} + \frac{x^n-\frac{(-1)^n}{n!}(1-x)(1-2x)(1-3x)\ldots(1-nx)}{(1-x)(1-2x)(1-3x)\ldots(1-nx)}\;.$$

Now you can deal with the remaining fraction. You already have the denominator in factorized form, so you know the partial fraction expansion will have the form

$$\frac{a_1}{1-x}+\frac{a_2}{1-2x}+\frac{a_3}{1-3x}+\ldots+\frac{a_n}{1-nx}\;.$$

To get the coefficients $a_i$, you can use the fact that the residues of the poles must be equal to the corresponding residues in the fraction.

-
Can you explain more? What are residues and poles? – Vafa Khalighi Mar 11 '11 at 12:07
Roughly speaking, a pole is a point $x_0$ at which the function diverges like $c/(x-x_0)$, and the residue at the pole is the coefficient $c$. For instance, the function $f(x)=(x^2+3)/((x-1)(x-2))$ has poles at $1$ and $2$, and the corresponding residues are $-4$ and $7$, which you can calculate by substituting the pole $x_0$ into the function except for the "pole part" of it, $1/(x-x_0)$. – joriki Mar 11 '11 at 12:12
I should add that you can also calculate the coefficients $a_i$ by bringing the partial fractions onto a common denominator and then comparing coefficients of powers of $x$ in the numerator with the fraction you're expanding, but that's often more tedious than using the residues of the poles. – joriki Mar 11 '11 at 12:14

To expand on joriki's comment, I claim that

$$\lim_{x \to \frac{1}{k}} \frac{x^n (1 - kx)}{(1 - x)...(1 - nx)} = a_k.$$

This is not hard to see by multiplying both sides by $1 - kx$. On the other hand, this limit is quite easy to compute since $1 - kx$ cancels, giving

$$a_k = \frac{1}{k(k-1)...(k-n)} = \frac{(-1)^{n-k}}{k! (n-k)!}.$$

Note that this technique works to give you the partial fraction decomposition of any rational function, at least when the denominator has simple roots: instead of canceling a factor, you can just use l'Hopital's rule.

Note also that the function you're looking at happens to be the ordinary generating function of the Stirling numbers of the second kind, and here you can cheat because you can also find their exponential generating function.

-

It is worth emphasizing that both of the presented solutions essentially employ what is known as Heaviside's cover-up method. As I explained in this answer, this method works generally, i.e. even for nonlinear denominators. As should be evident from the presentation that I gave there, the solution can be constructed by a purely algebraic deterministic algorithm, i.e. without employing any analytic techniques (residue calculus, limits, L'Hopital's rule, etc). Moreover, this is frequently the most efficient way to proceed - even for manual calculations.

-
@ Bill: Thanks for the helpful wiki article. It actually was 100% useful for a change :) – night owl Jul 4 '11 at 17:16