> [!NOTE] Lemma (Hockey Stick Identity for Binomial Coefficients) > Let $1\leq k\leq n.$ Then ${n \choose k} = \sum_{i=k-1}^{n-1} {i \choose k-1}$ ###### Combinatorial proof (partitioning by maximum element) Recall that ${n \choose k} := \# \{S \subseteq [n] \mid \# S = k\} := \# {[n] \choose k}.$Let $i$ be the largest element of any $k$-element subset of $[n]$. Then $i \in \{ k, k+1, \dots, n \}$: a subset of $[n]$ whose maximum element is $i$ has at most $i$ elements. For $i \in \{ k, k+1, \dots, n \}$, let $A_{i}$ be denote the set of $k$-element subsets of $[n]$ whose maximum element is $i$. Then the $A_{i}$ clearly form a partition of ${[n] \choose k}$ and so $\binom{n}{k} = \#A_{k} + \#A_{k+1} + \dots +\#A_{n}\tag{1}$ Now we claim that $\#A_{i} = {i-1 \choose k-1}$. To see that this observe that $f: A_{i} \to \{ S \subset [i-1] \mid \# S = k-1 \}; \quad S \mapsto S \setminus \{ i \}$is: well-defined, since $S \in A_{i}$ implies that $S\setminus \{ i \}\subset [i-1]$ and also $\#(S \setminus \{ i \} )=k-1$; and is bijective since its inverse is the function that adjoins $i$ to a set. Substituting in $(1)$ gives ${n \choose k} = \binom{k-1}{k-1} + \binom {k}{k-1}+ \dots + \binom {n-1}{k-1},$as required. $\blacksquare$ ###### Combinatorial proof (using stars-and-bars)