Chứng minh đếm hai cách của một đẳng thức nhị thức

Xét một tập gồm $2n$ người, trong đó có $n$ nam và $n$ nữ. Ta đếm, theo hai cách, số cách chọn một ủy ban đúng $n$ người từ tập $2n$ người này.

Trực tiếp, theo định nghĩa, số này là $\binom{2n}{n}$, vì ta chỉ đơn giản chọn $n$ đối tượng trong $2n$.

Cách khác, chia mọi ủy ban hợp lệ theo số nam nó chứa. Nếu ủy ban chứa đúng $k$ nam, với một số $k$ nào đó thỏa $0 \le k \le n$, thì $k$ nam đó có thể chọn theo $\binom{n}{k}$ cách, và $n-k$ thành viên còn lại phải là nữ, chọn từ $n$ nữ theo $\binom{n}{n-k}$ cách. Theo đẳng thức đối xứng $\binom{n}{n-k} = \binom{n}{k}$, số ủy ban với đúng $k$ nam là $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$.

Mọi ủy ban hợp lệ $n$ người đều có một số nam $k$ xác định giữa $0$ và $n$, và không ủy ban nào bị đếm hai lần ở các giá trị $k$ khác nhau, nên tổng theo mọi $k$ cho tổng số ủy ban là $\sum_{k=0}^{n} \binom{n}{k}^2$.

Vì cả hai biểu thức đếm đúng cùng một tập ủy ban, chúng phải bằng nhau: $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.