Proof using Generating Functions

Question

I need to use generating functions to show that

$$\sum_{r=1}^n r\binom{n}{r}\binom{m}{r} = n\binom{n+m-1}{n}$$

I have the generating functions for the right-hand side, which is

$$\frac{mx}{(1-x)^{m+1}}$$

Then the coefficient of $x^n$ is $n\binom{n+m-1}{n}$, but I do not know how to proceed for the left-hand side.

Answer 1

Here is a variation with $$(1+x)^{n+m-1}=\sum_{k=0}^{n+m-1}\binom{n+m-1}{k}x^k$$ as generating function. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. This way we can write for instance \begin{align*} \binom{n+m-1}{n}=[x^n](1+x)^{n+m-1}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{r=1}^nr\binom{n}{r}\binom{m}{r}} &=m\sum_{r=1}^n\binom{n}{r}\binom{m-1}{m-r}\tag{2}\\ &=m\sum_{r=1}^n\binom{n}{r}[x^{m-r}](1+x)^{m-1}\tag{3}\\ &=m[x^m](1+x)^{m-1}\sum_{r=1}^n\binom{n}{r}x^r\tag{4}\\ &=m[x^m](1+x)^{m-1}\left((1+x)^n-1\right)\tag{5}\\ &=m[x^m](1+x)^{n+m-1}\tag{6}\\ &=m\binom{n+m-1}{m}\tag{7}\\ &\,\,\color{blue}{=n\binom{n+m-1}{n}}\tag{8} \end{align*}

Comment:

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

• In (3) we use the coefficient of operator according to (1).

• In (4) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (5) we apply the binomial theorem.

• In (6) we multiply out and ignore the second term $1$ since it does not contribute to $[x^m]$.

• In (7) we select the coefficient of $x^m$.

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