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


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.


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*}


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


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


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*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.