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$?
 A: 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}
$$
A: 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.
