combinatorics - Double counting proof of binomial problem

The assignment is to prove the following assertion using the method of double counting and explaining which pairs were counted.

$$\dbinom{n+1}{k+1} = \sum_{i = k}^{n} \dbinom{i}{k}$$

Left side is choosing $k+1$ elements from a set of $n+1$ elements. To prove the right side I thought about removing the element $a_{i+1}$ from my base set $\{a_1, \dots, a_{n+1}\}$ and then choosing $k$ elements from the set $\{a_1, \dots, a_i\}$ and adding $a_{i+1}$ afterwards. This would give me all the required subsets.

The question is though how to formally describe the pairs I counted (if this is a good way to count it) in a relation or similar.

Answer

Let $I = \{0,\ldots,n\}$ and fix $k$. The left hand side counts all subsets of $I$ of size $k+1$. Call those subsets $P$.

Now $P = \cup_m P_m$ where $P_m$ are all subsets $A$ in $P$ that have $\max(A) = m$. This is a disjoint union, so we can sum the cardinalities.

Now, the maximal value can only be $k$ or more (as there are only $m+1$ elements that are $\le m$, and we need $k+1$ many), and at most $n$ of course.

To construct a set in $P_m$, we just pick $k$ points from $\{0,\ldots,m-1\}$ (which has $m$ many elements) and add $m$ to it. This exactly gets us all sets in $P_m$. And so $|P_m| = \binom{m}{k}$.

So $$\binom{n+1}{k+1} = |P| = \sum_{i=k}^n |P_i| = \sum_{i=k}^n \binom{i}{k}$$