Prove by induction that $\sum\limits_{k=m}^{n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$.

Question

Prove by induction that $\displaystyle\sum\limits_{k=m}^{n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$.

I am not sure how to perform the induction and what the base case is. But by trying to induct on $n$, we note that when $n=m$ the equality is $$\binom{m}{m}\binom{m}{m}=\binom{m}{m}2^{m-m}$$ which is true because both sides equal $1$. For the inductive step, suppose $\sum\limits_{k=m}^{n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$ is true. Then we need to show that $$\sum\limits_{k=m}^{n+1}{n+1\choose k}{k\choose m}=\binom{n+1}{m}2^{n+1-m}.$$ I am stuck here. Or is it better to induct on $m$?

Answer 1

you can get by without induction if you observe: $$ \binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m} $$ then $$ \sum_{k=m}^n \binom{n}{k} \binom{k}{m} = \binom{n}{m}\sum_{j=0}^{n-m}\binom{n-m}{j} = \binom{n}{m}2^{n-m} $$

Answer 2

We may write the required equality as $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{m}=\binom{n}{m}\,2^{n-m}$$ for all integers $n,m\geq 0$, using the convention that $\displaystyle\binom{p}{q}=0$ for integers $p,q\geq 0$ such that $p<q$. We shall prove by induction on $m$ the generalized statement: $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{m}\,x^{k-m}=\binom{n}{m}\,(1+x)^{n-m}\,,$$ where $x:=1$ leads to the required equality. The basis step is $m=0$, where we have the well known Binomial Theorem $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{0}\,x^{k-0}=\sum_{k=0}^n\,\binom{n}{k}\,x^k=(1+x)^n=\binom{n}{0}\,(1+x)^{n-0}\,.$$

Now, suppose the identity is true when $m=s$ for some integer $s\geq 0$ (and for all integer $n\geq 0$). Therefore, we have $$\sum_{k=0}^{n}\,\binom{n}{k}\,\binom{k}{s}\,x^{k-s}=\binom{n}{s}\,(1+x)^{n-s}\,.$$ for all integer $n\geq 0$. Taking the derivative with respect to $x$, we obtain $$\sum_{k=0}^{n}\,\binom{n}{k}\,\binom{k}{s}\,(k-s)\,x^{k-s-1}=\binom{n}{s}\,(n-s)\,(1+x)^{n-s-1}\,.$$ Dividing both sides by $s+1$ to get $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{s}\,\frac{k-s}{s+1}\,x^{k-(s+1)}=\binom{n}{s}\,\frac{n-s}{s+1}\,(1+x)^{n-(s+1)}\,.$$ Since $\displaystyle\binom{p}{s}\,\frac{p-s}{s+1}=\binom{p}{s+1}$ for every integer $p\geq 0$, we get the desired equality $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{s+1}\,x^{k-(s+1)}=\binom{n}{s+1}\,(1+x)^{n-(s+1)}\,,$$ establishing that the required equality holds for $m=s+1$. By induction, we are done.

---

Alternatively, consider a task of choosing a committee from $n$ people, where $m$ committee members are given the chief status. If the committee has $k$ members, then there are $\displaystyle\binom{n}{k}$ ways to choose the committee and $\displaystyle\binom{k}{m}$ ways to choose the chiefs. Hence, the number of ways to perform this task is precisely $\displaystyle\sum\limits_{k=m}^n\,\binom{n}{k}\,\binom{k}{m}$. On the other hand, we may chose $m$ chiefs first, whereby there are are $\displaystyle\binom{n}{m}$ ways to do so. The non-chief committee members are then selected from $n-m$ remaining people, which can be done in $2^{n-m}$ ways. Hence, we can perform this task in $\displaystyle\binom{n}{m}\,2^{n-m}$ ways. The proof is now complete.