3
$\begingroup$

$\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k} = \binom{n+1}{2k+1}, n\ge2k\ge0$

An combinatorial proof of the identity above states as follow:

(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $\binom{n+1}{2k+1}$

(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $\binom{m}{k}\binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-k\ge m\ge k$, there are total $\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k}$ ways.

Since (1)=(2), the statement is true. But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?

$\endgroup$
  • $\begingroup$ Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$. $\endgroup$ – Lord Shark the Unknown Jan 1 '18 at 11:22
1
$\begingroup$

Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{m=k}^{n-k}}&\color{blue}{\binom{m}{k}\binom{n-m}{k}}\\ &=\sum_{m=0}^{n-2k}\binom{m+k}{m}\binom{n-m-k}{k}\tag{1}\\ &=\sum_{m=0}^{n-2k}\binom{-k-1}{m}(-1)^m\binom{n-m-k}{k}\tag{2}\\ &=\sum_{m=0}^\infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}\tag{3}\\ &=[u^k](1+u)^{n-k}\sum_{m=0}^\infty\left(\frac{1}{1+u}\right)^{m}[z^m](1-z)^{-k-1}\tag{4}\\ &=[u^k](1+u)^{n-k}\left(1-\frac{1}{1+u}\right)^{-k-1}\tag{5}\\ &=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}\tag{6}\\ &=[u^{2k+1}](1+u)^{n+1}\tag{7}\\ &\color{blue}{=\binom{n+1}{2k+1}}\tag{8} \end{align*} and the claim follows.

Comment:

  • In (1) we shift the index to start with $m=0$ and use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

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

  • In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $\infty$ without changing anything since we are adding zeros only.

  • In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (5) we apply the substitution rule of the coefficient of operator with $z=\frac{1}{1+u}$
    \begin{align*} A(u)=\sum_{m=0}^\infty a_m u^m=\sum_{m=0}^\infty u^m [z^m]A(z) \end{align*}

  • In (6) we do some simplifications.

  • In (7) we do some more simplifications and apply the same rule as we did in (4).

  • In (8) we select the coefficient of $u^{2k+1}$.

$\endgroup$
0
$\begingroup$

More generally:

Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have \begin{equation} \dbinom{n+1}{x+y+1}=\sum_{m=0}^{n}\dbinom{m}{x}\dbinom{n-m}{y}. \end{equation}

This equality rewrites as \begin{equation} \dbinom{n+1}{x+y+1} = \sum_{m=x}^{n-y} \dbinom{m}{x}\dbinom{n-m}{y} , \end{equation} because all addends $\dbinom{m}{x}\dbinom{n-m}{y}$ are zero except for those where $x \leq m \leq n-y$.

Your identity is the particular case of the latter equality for $x = k$ and $y = k$.

Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $\left(x+y+1\right)$-element subset of $\left\{1,2,\ldots,n+1\right\}$ according to the value of the $\left(x+1\right)$-th-lowest element of the subset. Indeed, for any given $m \in \left\{0,1,\ldots,n\right\}$, picking an $\left(x+y+1\right)$-element subset $S$ of $\left\{1,2,\ldots,n+1\right\}$ whose $\left(x+1\right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $\left\{1,2,\ldots,m\right\}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $\left\{m+2,m+3,\ldots,n+1\right\}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $\dbinom{m}{x}\dbinom{n-m}{y}$ for the number of choices.

As for other proofs:

$\endgroup$

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.