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

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$$?

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}$$
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. 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.