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}$.

Answer 2

Hint : $\binom{n}{r}x^n=\frac{1}{r!} x^r \frac{d^r}{dx^r} x^{n}$

Using it you can find \begin{align*} \sum_{n=0}^{\infty}\sum_{r=1}^n r\binom{n}{r}\binom{m}{r}x^n &= \sum_{r=1}^n r \binom{m}{r} \sum_{n=r}^{\infty} \binom{n}{r} x^n\\ &= \sum_{r=1}^n r \binom{m}{r}\frac{1}{r!} x^r \frac{d^r}{dx^r} \sum_{n=r}^{\infty} x^{n}\\ &=\dots \end{align*}

Answer 3

If generating functions are insisted upon I would write

$$\sum_{r=1}^n r {n\choose r} {m\choose r} = \sum_{r=0}^n r {m\choose r} {n\choose n-r}.$$

Now what we have here is the Cauchy Product of two series

$$f(z) = z ((1+z)^m)' = m z (1+z)^{m-1} \quad\text{and}\quad g(z) = (1+z)^n.$$

The desired sum is the coefficient on $[z^n]$ of $f(z) g(z)$ or $$[z^n] f(z) g(z) = [z^n] m z (1+z)^{n+m-1}.$$

The right is the generating function we wanted to find: $$h(z) = f(z) g(z) = m z (1+z)^{n+m-1}.$$

We can extract the coefficient to get

$$ m [z^{n-1}] (1+z)^{n+m-1} = m {n+m-1\choose n-1} = m\frac{(n+m-1)!}{(n-1)! \times m!} \\ = n\frac{(n+m-1)!}{n! \times (m-1)!} = n {n+m-1\choose n}.$$

Here we have used the fact that for formal power series (this is the Cauchy Product)

$$[z^n] f(z) g(z) = \sum_{r=0}^n [z^r] f(z) [z^{n-r}] g(z).$$