generating function backtransformation

Question

i have been working with generating functions and i am fed up with always doing the partial fraction decomposition. i have found the following trick that can (hopefully) skip pfd.

$$ \frac{z^j}{(1-z)^k} \iff \sum_{n\geq 0} \binom{n+k-1-j}{k-1} \cdot z^n $$ i would like to prove it, however i seem to lack the skills to do so. can anyone confirm whether the proposed trick is actually valid? thanks in advance

Answer 1

This is a binomial series expansion. We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

Starting with the LHS we derive \begin{align*} \color{blue}{[z^n]\frac{z^j}{(1-z)^{k}}}&=[z^{n-j}]\frac{1}{(1-z)^k} =\binom{-k}{n-j}(-1)^{n-j}\tag{1}\\ &=\binom{n-j+k-1}{n-j}\tag{2}\\ &\color{blue}{=\binom{n-j+k-1}{k-1}}\tag{3} \end{align*} and the claim follows.

Comment:

• In (1) we use $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We apply the binomial series expansion and select the coefficient $z^{n-j}$.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we use $\binom{p}{q}=\binom{p}{p-q}$.