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

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!

• I know for sure that there is a combinatorial approach but I did this a long time ago, I'll ask some friend if he remembers Commented Jun 28, 2023 at 16:28
• @JulesBesson Thank you!
– Lior
Commented Jun 28, 2023 at 16:30

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.