# Partial fraction decomposition help

In a text that I am reading, they state that the following partial fraction ($r$ fixed) expansion is "readily computed":

$$f(z) = \frac{z^r}{(1-z)(1-2z)(1-3z)\cdots (1-rz)} = \frac{1}{r!} \sum_{j=0}^r \binom rj \frac{(-1)^{r-j}}{1-jz}$$

I know how to do partial fractions, or at least I thought I did. I tried to set it up with something like $$\frac{A_1}{1-z} + \frac{A_2}{1-2z} + \cdots + \frac{A_r}{1-rz}$$ but it got messy. Also, the answer given above has a constant term $\frac{(-1)^{r}}{r!}$ when $j=0$, which shouldn't show up when doing this method normally.

Could someone point me in the right direction? Thanks!

I now see why the constant term is necessary; doing a "long division" would result in the $\frac{(-1)^r}{r!}$ term. The remainder would be something like $$\frac{z^r - \frac{1}{r!}(1-z)(1-2z)\cdots(1-rz)}{(1-z)(1-2z)\cdots(1-rz)}$$ which technically could be solved by partial fractions...

Induction also looks promising, as suggested by Maesumi.

• The first thing to do is to convince ourselves that this equation produces correct results. When $r = 1$, we have $z/(1-z) = -1/(z-1)-1$. When $r = 2$, we have $z^2/((1-2 z) (1-z)) = -1/(2 (2 z-1))+1/(z-1)+1/2$ $\ldots$. Notice that in both cases we have a constant. Use the Summation and make sure you get the same thing as I used another approach. Next, are you trying to derive or prove the result? – Amzoti May 26 '13 at 21:43
• The constant term is necessary because power of numerator and denominator are equal to $r$. Saying it is "readily computed" could be author's humor! So don't feel bad if it is not obvious. Have you tried induction? – Maesumi May 26 '13 at 21:53
• Try to use the formula I introduced in this problem. – Mhenni Benghorbal Jun 17 '13 at 20:58

The coefficient of $\frac{1}{1-kz}$ is $$\left[\frac{z^r}{(1-z)(1-2z)(1-3z)\cdots\widetilde{(1-kz)}\cdots (1-rz)}\right]_{r=\frac{1}{z}}=\frac{\left(\frac{1}{k}\right)^r}{(1-\frac{1}{k})(1-2\frac{1}{k})(1-3\frac{1}{k})\cdots\widetilde{(1-k\frac{1}{k})}\cdots (1-r\frac{1}{k})}=\frac{1}{k(k-1)(k-2)\cdots\widetilde{0}(-1)(-2)\cdots(k-r)}=\frac{1}{r!} \binom rj (-1)^{r-j}$$
Multiply by $\frac{1}{1-jz}$ and plug in $\frac{1}{j}$ to get \begin{align*} A_j&=\frac{1/j^r}{\left( 1-\frac{1}{j} \right)\left( 1-\frac{2}{j} \right)\cdots \left( 1-\frac{j-1}{j} \right)\left( 1-\frac{j+1}{j} \right)\cdots \left( 1-\frac{r}{j} \right)} = \\ &= \frac{1}{j\left( j-1 \right)\left( j-2 \right)\cdots \left( j-j+1 \right)\left( j-j-1 \right)\cdots \left( j-r \right)}= \\ &= \frac{1}{\underbrace{j\left( j-1 \right)\left( j-2 \right)\cdots 1}_{j!} \cdot \underbrace{(-1)(-2) \cdots (-(r-j))}_{(-1)^{r-j}(r-j)!}}= \\ &= \Big\{\binom{r}{j} = \frac{r!}{j!(r-j)!}\Big\}= \frac{1}{r!}\binom{r}{j}\left( -1 \right)^{r-j} \end{align*}
By polynomial division, we can write \begin{equation} \frac{z^r}{(1-z)(1-2z)\cdots (1-rz)}=q+\frac{c}{(1-z)(1-2z)\cdots (1-rz)}\tag{1} \end{equation} where $q, c\in \mathbb{R}$. By theory of partial fractions, we can have at most $r$ fractions, so by the above, we get \begin{equation*} \frac{c}{(1-z)(1-2z)\cdots (1-rz)}=\sum_{j=1}^{r}\frac{A_j}{1-jz} \end{equation*} Plugging in $0$ in (1), we thus obtain \begin{align*} q=A_0&=-\frac{1}{r!}\sum_{j=1}^{r}\binom{r}{j} \frac{(-1)^{r-j}}{1-0}= \\ &=-\frac{1}{r!}\Big[\underbrace{\sum_{j=0}^{r}\binom{r}{j}(-1)^{r-j}}_{(1-1)^r=0}-\binom{r}{0}(-1)^r \Big]=\frac{(-1)^r}{r!} \end{align*}