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$?
Best Answer
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} $$