The numbers $\binom{n}{k}$ fill Pascal's triangle, and you have used them to count combinations. They satisfy many identities. Algebra can prove them, but a counting argument usually explains why they hold, using nothing but subsets.
Key idea
A combinatorial proof shows two expressions are equal by showing they count the same set in two different ways. Examples: Pascal's identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$; the row sum $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^{n}$; symmetry $\binom{n}{k} = \binom{n}{n-k}$.
Why it works
For Pascal's identity, count groups of $k$ people chosen from $n$, one of whom is Ana. Every group either contains Ana or does not. With Ana: choose her partners, $\binom{n-1}{k-1}$ ways. Without Ana: choose all $k$ from the other $n - 1$, $\binom{n-1}{k}$ ways. These cases are disjoint and cover everything, so the sum rule gives $\binom{n}{k}$ on the left. The same idea in a grid: the number of shortest paths to a point is the number arriving from the left plus the number arriving from below.
Worked examples
Worked example: Using Pascal's identity
Given $\binom{9}{3} = 84$ and $\binom{9}{4} = 126$, find $\binom{10}{4}$.
- Pascal: $\binom{10}{4} = \binom{9}{3} + \binom{9}{4}$.
- $84 + 126 = 210$.
Answer: $210$
Worked example: The row sum, two ways
Show that $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^{n}$.
- Count the subsets of an $n$-element set. By size: there are $\binom{n}{k}$ subsets of size $k$, and adding over $k$ gives the left side.
- By decisions: each element is in or out, so there are $2^{n}$ subsets.
- Same set, two counts: they are equal. (The binomial theorem gives the same result from $(1 + 1)^{n}$.)
Answer: Both sides count the subsets of an $n$-element set.
Worked example: Committees with a chair
Show that $k\binom{n}{k} = n\binom{n-1}{k-1}$.
- Count committees of $k$ people from $n$, with one member named chair.
- Committee first, then chair: $\binom{n}{k}$ committees, then $k$ choices of chair.
- Chair first, then the rest: $n$ choices of chair, then $\binom{n-1}{k-1}$ ways to fill the other seats.
Answer: Both sides count committees with a chair.
Common mistake
Checking one value of $n$ and calling it proved. Verifying $\binom{5}{2} = \binom{4}{1} + \binom{4}{2}$ ($10 = 4 + 6$) is a good sanity check, but an identity claims something for every $n$ and $k$. Check: a proof must work for general $n$ and $k$; a counting argument does this by describing one set and two ways to count it, with no specific numbers.