Complicated partial fraction expansion

Question

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!

Answer 1

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

Answer 2

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

$$\alpha_r=\frac{r^{k-1}}{\underbrace{(r-1)(r-2)\cdot(r-(r-1))}_{(r-1)!}\underbrace{(r-(r+1))\cdots(r-k)}_{(-1)(-2)\cdots(-(k-r))}}$$

and then rewriting this as

$$\alpha_r=\frac{r^{k-1}}{(r-1)!(-1)^{k-r}(k-r)!}=(-1)^{k-r}\frac{r^{k-1}}{(r-1)!(k-r)!}\;.$$

Answer 3

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 :)