Induction proof (combinatorics): $\sum_{k=0}^{n}{n\choose k}{k\choose m} = {n\choose m}2^{n-m}$

Question

I had a question. I don't know how to end my solution: $$\sum_{k=0}^{n}{n\choose k}{k\choose m} = {n\choose m}2^{n-m}$$ for $n = 0$ $${0\choose 0}{0\choose m} = {0\choose m}2^{0-m}$$ if $m=0$: both equal $1$, if $m>0$: both equal $0$. Suppose it holds for :$$\sum_{k=0}^{n-1}{n-1\choose k}{k\choose m} = {n-1\choose m}2^{n-m-1}$$ now: $$\sum_{k=0}^{n}{n-1\choose k}{k\choose m} + {n\choose n}{n\choose m}= {n\choose m}2^{n-m}$$ $${n-1\choose m}2^{n-m-1} + {n\choose m} = {n\choose m}2^{n-m} $$ now I don't know how to continue it, maybe I did a mistake that it is misleading me. Can you help me?

Answer 1

Inductive Proof

I would start the induction from $n=m$, where both sum and formula are $1$, and then use the inductive step $$ \begin{align} \sum_{k=m}^n\color{#C00}{\binom{n}{k}}\binom{k}{m} &=\sum_{k=m}^n\left[\color{#C00}{\binom{n-1}{k}}\binom{k}{m}+\color{#C00}{\binom{n-1}{k-1}}\color{#090}{\binom{k}{m}}\right]\\ &=\sum_{k=m}^n\left[\binom{n-1}{k}\binom{k}{m}+\binom{n-1}{k-1}\color{#090}{\binom{k-1}{m}}+\binom{n-1}{k-1}\color{#090}{\binom{k-1}{m-1}}\right]\\ &=\binom{n-1}{m}\color{#00F}{2^{n-1-m}}+\binom{n-1}{m}\color{#00F}{2^{n-1-m}}+\binom{n-1}{m-1}2^{n-m}\\ &=\color{#E80}{\binom{n-1}{m}}\color{#00F}{2^{n-m}}+\color{#E80}{\binom{n-1}{m-1}}2^{n-m}\\ &=\color{#E80}{\binom{n}{m}}2^{n-m} \end{align} $$

---

Combinatoric Proof

Suppose we want to distribute $m$ pairs of shoes among $n$ people. Everyone who gets a pair of shoes gets a pair of socks, and the rest of the people can get a pair of socks or not.

We can break things down by how many pairs of socks we want to give out. We have $n$ people and choose $k$ to wear socks. From those $k$, we want to choose $m$ to wear shoes. The number of ways to distribute shoes and socks is $$ \sum_{k=m}^n\binom{n}{k}\binom{k}{m} $$ Another way to look at this is to distribute the $m$ shoes, and the required socks, among the $n$ people, then distribute socks or no socks to the $n-m$ people who don't have shoes. The number of ways to distribute shoes and socks is $$ \binom{n}{m}2^{n-m} $$ Since these two formulas count the same thing in different ways, we have $$ \sum_{k=m}^n\binom{n}{k}\binom{k}{m}=\binom{n}{m}2^{n-m} $$

---

Another Approach

Note that $$ \begin{align} \binom{n}{k}\binom{k}{m} &=\frac{n!}{k!(n-k)!}\frac{k!}{m!(k-m)!}\\ &=\frac{n!}{(n-m)!m!}\frac{(n-m)!}{(n-k)!(k-m)!}\\ &=\binom{n}{m}\binom{n-m}{k-m} \end{align} $$ Then recalling that $\sum\limits_{k=m}^n\binom{n-m}{k-m}=2^{n-m}$, we get $$ \begin{align} \sum_{k=m}^n\binom{n}{k}\binom{k}{m} &=\sum_{k=m}^n\binom{n}{m}\binom{n-m}{k-m}\\ &=\binom{n}{m}2^{n-m} \end{align} $$