I'm reading the book generatingfunctionology by Herbert Wilf and I came across a partial fraction expansion on page 20 that I cannot understand. The derivation is as follows:

$$ \frac{1}{(1-x)(1-2x)...(1-kx)} = \sum_{j=1}^{k} \frac{\alpha_j}{1-jx} $$

The book says to fix $r, 1 \leq r \leq k$, and multiply both sides by $1-rx$. Doing so, I get:

$$ \frac{1}{(1-x)...(1-(r-1)x)(1-(r+1)x)...(1-kx)} = \frac{\alpha_1(1-rx)}{1-x} + ... + \frac{\alpha_{r-1}(1-rx)}{1-(r-1)x} + \alpha_r + \frac{\alpha_{r+1}(1-rx)}{1-(r+1)x} + ... + \frac{a_k(1-rx)}{1-kx} $$

Contrarily, the book has:

$$ \alpha_r = \frac{1}{(1-x)...(1-(r-1)x)(1-(r+1)x)...(1-kx)} $$

I don't understand how the other other fractions on the right side of my result cancel out to $0$. I tried with a small example where $k=3$ and I couldn't isolate $\alpha_2$ nicely after multiplying both sides by $1-2x$. Any pointers on this would be greatly appreciated.

After this, the book goes on by letting $x=1/r$, resulting in the following:

$$ \begin{aligned} \alpha_r &= \frac{1}{(1-1/r)(1-2/r)...(1-(r-1)/r)(1-(r+1)/r)...(1-k/r)} \\ &= (-k)^{k-r}\frac{r^{k-1}}{(r-1)!(k-r)!} && (1 \leq r \leq k) \end{aligned} $$

I also can't figure how this is derived (I suspect it's using an identity that I'm not aware of.) Any help would be much appreciated. Thanks a lot!


3 Answers 3


It appears that the $\alpha_j$ coefficients are being computed by the standard Heaviside method (sometimes called the "cover up" method).

Heaviside's Method for partial fraction expansion


My edition of the book doesn’t have

$$\alpha_r = \frac{1}{(1-x)\ldots(1-(r-1)x)(1-(r+1)x)\ldots(1-kx)}\;,$$

which in any case makes no sense, since $\alpha_r$ is a constant and the righthand side is not. However, after letting $x=\frac1r$ it does show

$$\begin{align*} \alpha_r&=\frac1{(1-1/r)(1-2/r)\cdots(1-(r-1)/r)(1-(r+1)/r)\cdots(1-k/r)}\\ &=(-1)^{k-r}\frac{r^{k-1}}{(r-1)!(k-r)!}\;. \end{align*}$$

The last step is obtained by first multiplying by $r^{k-1}$ to get


and then rewriting this as



To find the coefficients of the expansion, you can follow the usual "cover" up rule which is essentially the results you have shown albeit buried in indices and what not: $$ \frac{1}{(1-x)(1-2x)...(1-kx)} = \sum_{j=1}^{k} \frac{\alpha_j}{1-jx} $$ say we would want to find an arbitrary $\alpha_j$ for some value of $j \in \{1,2,...,k\}$. We call this $r$ to emphasise, and to avid confusion with the summation index. So we multiply both sides by $1-rx$ $$ \frac{1-rx}{(1-x)(1-2x)...(1-kx)} = \sum_{j=1}^{k} \alpha_j\frac{1-rx}{1-jx} $$ Since $r$ will coincide with one of the $j$'s we can "pull this out" from the right hand side $$ RHS = \alpha_r + \sum_{\underset{j\ne r}{j=1}}^{k} \alpha_j\frac{1-rx}{1-jx} $$ And for the left hand side, the r will "cancel" on one of the denominator factors: $$ LHS = \frac{1}{\underset{\text{without the $1-rx$}}{(1-x)(1-2x)...(1-kx)}} $$ The expansion holds for all values of x so we can set $x=1/r$, and simplify both sides to get the result. I'll stop here because I think doing it is fun :)


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.