Proof that $\sum_{k=0}^n {n \choose k}{k \choose m} = {n \choose m}2^{n-m}$

Question

Can someone suggest a proof using generating functions? if possible

$$\sum_{k=0}^n {n \choose k}{k \choose m} = {n \choose m}2^{n-m} $$

Moreover, do both sides of the equation count the number of subsets of $n-m$ elements out of $n$ elements?

Thanks in advance.

Answer 1

What the sides count is a bit more complicated than "The number of subsets of $n-m$ elements". First note that because of the $\binom{k}{m}$, the sum on the left side might as well be $\sum_{k = m}^n$. From there the combinatorial argument goes a bit like this:

Right hand side: Out of $n$ (distinguishable) balls, pick $m$ of them and set aside. With the rest, paint each one either red or blue.

Left hand side: Out of $n$ balls, pick $k$ to put aside, and paint the rest blue. Now from the $k$ balls put aside, pick $m$, put them aside, and paint the rest red.

All in all, what they count is the number of ways to pick out $m$ balls that are not painted, and then paint the rest of the balls either red or blue.

Answer 2

I’ll give first a combinatorial argument, since that shows most clearly what is being counted. As usual $[n]=\{1,\ldots,n\}$. $\binom{n}k\binom{k}m$ is the number of ways to choose a set $S\subseteq[n]$ of cardinality $k$ and then choose an $m$-element subset $M$ of $S$; the result is to divide $[n]$ into the pairwise disjoint sets $M,S\setminus M$, and $[n]\setminus S$. Summing over $k$ gives us the number of ways to divide $[n]$ into pairwise disjoint sets $M,A$, and $B$ such that $|M|=m$. We can count the same thing by observing that there are $\binom{n}m$ ways to choose $M$, after which we can choose any one of the $2^{n-m}$ subsets of $[n]\setminus M$ to be $A$; this can be done in $\binom{n}m2^{n-m}$ ways.

An algebraic argument is very straightforward:

$$\begin{align*} \sum_{k=0}^n\binom{n}k\binom{k}m&=\sum_{k=0}^n\binom{n}m\binom{n-m}k\\ &=\binom{n}m\sum_{k=0}^n\binom{n-m}k\\ &=\binom{n}m2^{n-m}\;. \end{align*}$$

Using generating functions seems a bit clumsy here.

Answer 3

Since you asked for a proof using generating functions, then you may consider that $$ \begin{gathered} \left( {1 + \left( {1 + x} \right)} \right)^{\,n} = \hfill \\ = \sum\limits_j {\left( \begin{gathered} n \\ j \\ \end{gathered} \right)2^{\,n - j} x^{\,j} } \hfill \\ = \sum\limits_k {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( {1 + x} \right)^{\,k} } = \sum\limits_j {\left( {\sum\limits_k {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( \begin{gathered} k \\ j \\ \end{gathered} \right)} } \right)x^{\,j} } \hfill \\ \end{gathered} $$

Answer 4

Here is a variation based upon the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain for $n\geq 0$: \begin{align*} \sum_{k=0}^n\binom{n}{k}\binom{k}{m} &=\sum_{k=0}^\infty[z^k](1+z)^n[u^m](1+u)^k\tag{1}\\ &=[u^m]\sum_{k=0}^\infty (1+u)^k[z^k](1+z)^n\tag{2}\\ &=[u^m](2+u)^n\tag{3}\\ &=[u^m]\sum_{k=0}^n\binom{n}{k}z^k2^{n-k}\tag{4}\\ &=\binom{n}{m}2^{n-m}\tag{5} \end{align*} and the claim follows.

Comment:

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

• In (2) we use the linearity of the coefficient of operator.

• In (3) we use the substitution rule with $z:=1+u$ \begin{align*} A(u)=\sum_{k=0}^\infty a_k u^k=\sum_{k=0}^\infty u^k [z^k]A(z) \end{align*}

• In (4) we expand the binomial.

• In (5) we select the coefficient of $u^m$.