> [!NOTE] Lemma (Pascal's rule for bijective coefficients) > For all natural numbers $n,k$ with $1\leq k \leq n,$ the [[Binomial Coefficient|binomial coefficient]] satisfies ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.$ ###### Combinatorial proof First, recall that $\binom{n}{k} \;=\; \bigl|\{\,A\subseteq\{1,2,\dots,n\}:|A|=k\}\bigr|$is the number $k$-element subsets of an $n$-element set.  Our goal is to show the identity $\binom{n}{k} \;=\; \binom{n-1}{k-1} \;+\; \binom{n-1}{k}.$ To prove this combinatorially, let $S$ be the collection of all $k$-element subsets of $\{1,2,\dots,n\}.$  Every such subset either contains the element 1 or it does not, so we may partition S into two disjoint parts: $S_1 \;=\;\{\,A\in S : 1\in A\} \quad\text{and}\quad S_2 \;=\;\{\,A\in S : 1\notin A\}.$ Since $S_1$ and $S_2$ partition $S$, we have $\,|S|=|S_1|+|S_2|.$  But $|S|=\binom{n}{k}$, so it remains to show that $|S_1|=\binom{n-1}{k-1}$ and $|S_2|=\binom{n-1}{k}$. Next, observe that for any $A\in S_1$ is a $k$-subset containing $1$, removing the element $1$ yields a $(k-1)$-subset of $\{2,3,\dots,n\}$.  This gives a bijection $f: S_1\;\longrightarrow\;\bigl\{\,B\subseteq\{2,\dots,n\}:|B|=k-1\bigr\}; \qquad f(A)=A\setminus\{1\},$whose inverse simply adjoins $1$ back to a $(k-1)$-subset. Therefore $|S_1| \;=\; \binom{n-1}{k-1}.$ Similarly, every $A\in S_2$ is already a k-subset of $\{2,3,\dots,n\}$, so the identity map $g: S_2\;\longrightarrow\;\bigl\{\,C\subseteq\{2,\dots,n\}:|C|=k\bigr\}; \qquad g(A)=A,$is a bijection.  Hence $|S_2| \;=\; \binom{n-1}{k}.$ Combining these counts yields $\binom{n}{k} \;=\; |S| \;=\; |S_1|+|S_2| \;=\; \binom{n-1}{k-1} \;+\; \binom{n-1}{k},$which completes the proof. $\blacksquare$ **Algebraic proof:** $\blacksquare$