Exercise 407Combinatorics › Binomial coefficientsHigh schoolAdded 3 Nov 2026

Pascal's identity

#Pascal identity#recurrence#binomial

Statement

Prove that $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ .

Hint

Combinatorial proof: classify $k$ -subsets of an $n$ -set by whether they contain a fixed element.

Show solutionHide solution

Setup. Let $S$ be an $n$ -set with a distinguished element $x$ . We count $k$ -subsets.

Case 1: contains $x$ . Then choose the remaining $k-1$ elements from $S\setminus\{x\}$ : $\binom{n-1}{k-1}$ .

Case 2: does not contain $x$ . Then choose all $k$ from $S\setminus\{x\}$ : $\binom{n-1}{k}$ .

Conclusion. $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ .