1

Let $a$ and $b$ be natural numbers such that $a \geq b \geq 1$. How can we evaluate the following sum? $$ \sum_{n=1}^{b}n\binom{a}{n}\binom{b}{n}$$

David E.
  • 28
  • At least for the case $a=b$, were you able to make some progress? – Sarvesh Ravichandran Iyer Sep 02 '17 at 03:26
  • I'd try to use identities like $n\binom an=a\binom{a-1}{n-1}$ and $\binom bn=\binom b{b-n}$. – Angina Seng Sep 02 '17 at 03:29
  • Not quite, @астонвіллаолофмэллбэрг – David E. Sep 02 '17 at 03:38
  • 1
    The sum when $a=b$ is the sum $\sum_{n=0}^{a} n \binom an^2$, the same as the sum $\sum_{n=0}^{a}n \binom an \binom a{a-n}$. Try to get a combinatorial interpretation of the right hand side in some manner. Think of it this way : there are $a$ boys and $a$ girls, and you need to choose a group of $a$ people amongst them, and appoint one girl the head of the group. The given expression is one way of counting this(the case $n = 0$ can be ignored in this interpretation), can you figure out another way? – Sarvesh Ravichandran Iyer Sep 02 '17 at 03:41
  • You could first choose one of the girls to be the head of the group, there are $a$ possibilities. From the remaining $2a-1$, you choose $a-1$, giving us a total of $a \binom{2a-1}{a-1}$ of possible configurations. – David E. Sep 02 '17 at 04:00
  • Now, if there are $a$ boys and $b$ girls and we still want groups of $a$, we could do something similar. This way, the answer is $b \binom{a+b-1}{a-1}=\frac{(a+b-1)!}{(a-1)!(b-1)!}$. Thank you very much @астонвіллаолофмэллбэрг , that was more than helpful. – David E. Sep 02 '17 at 04:07
  • I always love a combinatorial interpretation. They are indeed some of the most beautiful proof techniques to exist. – Sarvesh Ravichandran Iyer Sep 02 '17 at 04:08

2 Answers2

2

For any polynomial $p(z) = a_0 + a_1 z + \cdots a_n z^n$, let $[z^k]p(z)$ be the coefficient $a_k$ for the monomial $z^k$ in $p(z)$. We have $$\begin{align}\sum_{n=1}^b n \binom{a}{n}\binom{b}{n} &= \sum_{n=0}^b \binom{a}{a-n}\times n\binom{b}{n} = \sum_{n=0}^b [z^{a-n}]\{(1+z)^a\} \times [z^n]\{z\frac{d}{dz}(1+z)^b\}\\ &= [z^a]\{(1+z)^a \times bz(1+z)^{b-1}\} = b[z^{a-1}]\{(1+z)^{a+b-1}\}\\ &= b\binom{a+b-1}{a-1} = \frac{(a+b-1)!}{(a-1)!(b-1)!} \end{align} $$

achille hui
  • 122,701
0

$$\begin{align} \sum_{n=1}^b n\binom an\binom bn &=\sum_{n=1}^b \binom an\cdot n\binom bn\\ &=\sum_{n=1}^b \binom an\cdot b\binom {b-1}{n-1}\\ &=b\sum_{n=1}^b \binom a{a-n}\binom {b-1}{n-1}\\ &=b\binom {a+b-1}{a-1} &&\text{(Vandermonde)}\\ &=b\binom {a+b-1}{b}\\ &=(a+b-1)\binom {a+b-2}{b-1} \\ &=(a+b-1)\binom {a+b-2}{a-1}\end{align}$$

Hypergeometricx
  • 22,657