# Combinatorial proof of $\sum_{i=0}^n {{i}\choose{ k}} = {{n+1}\choose{ k+1}}$

It’s easy to prove $\sum_{i=0}^n {{i}\choose{ k}} = {{n+1}\choose{ k+1}}$ by induction with ${{n}\choose{ k}} = {{n-1}\choose{ k-1}} + {{n}\choose{ k-1}}$, but what is its combinatorial proof?

#### Solutions Collecting From Web of "Combinatorial proof of $\sum_{i=0}^n {{i}\choose{ k}} = {{n+1}\choose{ k+1}}$"

How many ways can we pick a subset of size $k+1$ from $n+1$? Let’s say the final element of our selection appears at index $i$. Then we need to pick $k$ elements from the previous $i-1$.

So the total number of ways is $$\sum_{i=1}^{n+1} \binom{i-1}{k} = \sum_{i=0}^n \binom{i}{k}$$