Proof of sum of binomials over upper index (induction)

Question

How would you proof $$ \sum_{m=k}^{n}\binom{m}{k} = \binom{n + 1}{k + 1} $$ with $n \geq k$ and $n$, $k \in \mathbb{N}$ by induction? I had some approaches but wasn't sure if they were right, so I'd appreciate if you could share some solutions!

Answer 1

The induction proof on $n$ reduces to Pascal's identity $$\binom{n+1}{k+1} + \binom{n+1}{k} = \binom{n+2}{k+1}.$$ But there is a nicer combinatorial proof of your identity. The right-hand side describes the number of ways of choosing a subset $S$ of $\{1,\ldots,n+1\}$ of size $k+1$. Let $m = \max S - 1$, so $k \leq m \leq n$. Then $S \setminus \{m+1\}$ is a subset of $\{1,\ldots,m\}$ of size $k$. This is what the left-hand side describes.