Exercise 439Combinatorics › Counting principlesHigh schoolAdded 3 Nov 2026

Pascal's identity

#Pascal identity#binomial#recurrence

Statement

Show that $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ for $1\le k\le n-1$ .

Hint

Use combinatorial proof or the algebraic formula.

Show solutionHide solution

Solution

Combinatorial proof. Choose $k$ elements from an $n$ -set $S$ . Fix element $x$ . The choice either includes $x$ : $\binom{n-1}{k-1}$ ways, or doesn't: $\binom{n-1}{k}$ ways. Sum gives $\binom{n}{k}$ .

Conclusion. Pascal's identity holds.

Consequence. Pascal's triangle.

Pascal's identity

Statement

Solution

More problems in Counting principles