Stuck in prove by induction with combinations.

Question

I want to proof by induction:

$ \sum_{k=m}^{n} {n \choose k}{k \choose m} = {n \choose m}2^{n-m}$

given that $n,m \in \mathbb{N}$ and $0 \leq m \leq n$

I have done that the proof for the first element $m=n$:

$ {n \choose m} = {n \choose m}$

but now when doing: $ \sum_{k=m}^{n+1} {n+1 \choose k}{k \choose m} = {n+1 \choose m}2^{(n+1)-m}$

I got stuck here: $\sum_{k=m}^{n+1} {n+1 \choose k}{k \choose m} = \sum_{k=m}^{n} {n+1 \choose k}{k \choose m} + {n+1 \choose k}{k \choose m}$

because of the usage of n+1 inside the sum... What am I missing here?

thanks!

Answer 1

Here is a direct proof :

Let $ n\in\mathbb{N} $, we have : $$ \left(\forall k\in\mathbb{N}\right),\ \binom{n}{k}\binom{k}{m}=\binom{n-m}{k-m}\binom{n}{m} $$

Thus $$ \sum_{k=m}^{n}{\binom{n}{k}\binom{k}{m}}=\binom{n}{m}\sum_{k=m}^{n}{\binom{n-m}{k-m}}=\binom{n}{m}\sum_{k=0}^{n-m}{\binom{n-m}{k}}=\binom{n}{m}2^{n-m} $$

Answer 2

Here's a combinatorial approach:

Hint: Out of $n$ students, how many ways are there to select $m$ of them to receive first class honors, and some(others) to receive second class honors?