Proof that $\sum_{k=0}^n {n \choose k}{k \choose m} = {n \choose m}2^{n-m}$ 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.
 A: 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.
A: 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} 
$$
A: 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.
A: 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$.
