Proof of $\sum_{k=m}^{n} \binom{n}{k} \binom{k}{m} = \binom{n}{m}2^{n-m}$

Question

I'm trying to prove combinatorial identities to prepare for a test. Here is one of them:

$$\forall 1\le m\le n:\sum_{k=m}^{n} \binom{n}{k} \binom{k}{m} = \binom{n}{m}2^{n-m}$$

This question has been answered here Stuck in prove by induction with combinations.. (algebraically).

I'd like to solve this in a combinatorial approach.

LHS:

Possible ways to choose $k$ elements from $n$ elements, then from those $k$ elements I choose $m$ elements.

RHS:

Possible ways to choose $m$ elements from $n$ elements. For the left $n-m$ elements I choose one of two options.

I understand that on both sides I get subsets of the $n$ elements that has to do something with 2 options, but I'm not sure what story combines both side of the equation. Any help or suggestions would be appreciated. Thank you!

Answer 1

Disclaimer

I believe I have seen a solution somewhere on this website but couldn't find it, so here is my solution.

Set Up

There are $n$ students, you want to have $m$ student to be starters of your basketball team, and maybe some reserve players as well.

Left Hand Side

Choose $k\geq m$ students to be part of the team. Out of these $k$ players, choose $m$ to be the starters. Summing up for all possible value of $k$, you get the total number of possibilities as given on the left hand side.

Right Hand Side

Choose $m$ students to be the starters. Each of the remaining $n-m$ students may or may not be a reserve player. Total number of possibilities is then given by the right hand side.

Conclusion

LHS and RHS count the same object, namely number of ways to choose $m$ starters and some reserve players out of $n$ students, so they must be equal.