2
$\begingroup$

Given the sum $$ \sum_{k=0}^{m} {n \choose k} {m \choose k}, $$ where $ n > m$. Could it be somehow calculated into a shorter an nicer expression which doesn't contain the sum?

Thanks in advance!

$\endgroup$
  • 4
    $\begingroup$ HINT: consider the expansions of $(1+x)^n$ and $(1+\frac{1}{x})^m$ and observe the coefficients $\endgroup$ – Ekaveera Kumar Sharma Jan 15 '16 at 9:39
  • $\begingroup$ You could try to calculate it for $m=0,1,2,3$ and see if there is a pattern. If you take ${n \choose k}=0$ when $n \lt k$ then you can also calculate it for $n \le m$ and the pattern may be even more obvious $\endgroup$ – Henry Jan 15 '16 at 9:50
6
$\begingroup$

We use the coefficient of operator $[x^m]$ to denote the coefficient of $x^m$ of a series. So, we can write e.g. $$\binom{m}{k}=[x^k](1+x)^m$$

We obtain for $a\geq 0$ \begin{align*} \sum_{k=0}^{m}&\binom{m+a}{k}\binom{m}{k}\\ &=\sum_{k=0}^{\infty}[x^k](1+x)^{m+a}[y^k](1+y)^m\tag{1}\\ &=[x^0](1+x)^{m+a}\sum_{k=0}^{\infty}x^{-k}[y^k](1+y)^m\tag{2}\\ &=[x^0](1+x)^{m+a}(1+\frac{1}{x})^m\tag{3}\\ &=[x^0](1+x)^{m+a}\frac{1}{x^m}(1+x)^m\\ &=[x^m](1+x)^{2m+a}\\ &=\binom{2m+a}{m} \end{align*}

Comment:

  • In (1) we use the coefficient of Operator and change the limit to $\infty$ without changing the sum, since we add only zero.

  • In (2) we use the linearity of the coefficient of operator and $[x^{n+k}]A(x)=[x^n]x^{-k}A(x)$

  • In (3) we use the substitution rule \begin{align*} A(x)=\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{\infty}x^k[y^k]A(y) \end{align*}

$\endgroup$
3
$\begingroup$

Note that

$$\sum_{k=0}^m\binom{n}k\binom{m}k=\sum_{k=0}^m\binom{n}k\binom{m}{m-k}\;.\tag{1}$$

Suppose that we have a pool of $n$ women and $m$ men, from which we are to choose a committee of $m$ people; clearly the righthand side of $(1)$ is the number possible committees, counted according to the number ($k$) of women on the committee.

On the other hand, we can simply choose any $m$ of the $n+m$ members of the pool. This can be done in $\binom{n+m}m$ ways, so

$$\sum_{k=0}^m\binom{n}k\binom{m}k=\sum_{k=0}^m\binom{n}k\binom{m}{m-k}=\binom{n+m}m\;.$$

This is an instance of Vandermonde’s identity, and the argument that I just gave is the usual combinatorial proof of it.

$\endgroup$
-1
$\begingroup$

it is related to a question I answered yesterday :

$$\sum_{k=0}^m {n \choose k} {m \choose k} = \frac1{2\pi}\int_0^{2\pi} (e^{ix}+1)^n (e^{-ix}+1)^m dx = \frac{2^{n+m}}{2\pi} \int_0^{2\pi}e^{ix(n-m)/2}\cos^{m+n}(x/2) dx $$

$\endgroup$
  • 3
    $\begingroup$ An integral is still a sum...? Is there a closed expression, I think the OP wanted to know? $\endgroup$ – Henno Brandsma Jan 15 '16 at 9:46
  • $\begingroup$ There is no closed form. Using Mathematica to carry out the integral it came out involved Gamma functions and Gauss's Hypergeometric or the Incomplete Beta function. $\endgroup$ – Ian Miller Jan 15 '16 at 10:20
  • $\begingroup$ @Ian Miller what you say is for the indefinite integral $\endgroup$ – reuns Jan 15 '16 at 10:33
  • $\begingroup$ Hmm I just looked at Mathematica's output again. I forgot to use the fact that $m$ and $n$ are integers. Factoring that it did make let Mathematica simplify the expression further: $$\frac{(-1)^n\cdot2^{1-m-n}\Gamma(-m)}{\Gamma(-m-n)\cdot\Gamma(1+n)}$$ I imagine this can simplify a bit now I look at it. $\endgroup$ – Ian Miller Jan 16 '16 at 2:38

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