Combinatorial Identities & Proofs
Two roads to the same truth. Algebraic proofs expand factorials and simplify step by step. Combinatorial proofs ask a single question — "what does each side count?" — and show that both sides count the same thing. Mastering both styles is essential for HSC Extension 1, where proof questions can appear from any angle. In this lesson you'll prove Pascal's identity, the symmetry rule, the hockey-stick identity, and the absorption identity.
You know $\binom{6}{2} = 15$ and $\binom{6}{4} = 15$. Without using a formula — can you explain in words why these two values must be equal? Write your best intuitive explanation before reading on.
There are two methods for proving combinatorial identities. Both are valid; the algebraic method uses factorials directly, while the combinatorial method argues by counting the same set two different ways.
Algebraic proof: Express $\binom{n}{r} = \dfrac{n!}{r!(n-r)!}$ for both sides, then simplify until LHS = RHS using factorial algebra. Every step must be reversible or explicitly justified.
Combinatorial proof: Describe a single counting problem. Show that the LHS counts it one way, and the RHS counts it another way. Since both count the same set, they must be equal.
Key identities
- Symmetry: $\binom{n}{r} = \binom{n}{n-r}$
- Pascal's identity: $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$
- Absorption: $r\binom{n}{r} = n\binom{n-1}{r-1}$
- Vandermonde: $\displaystyle\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$
Proof techniques
- Algebraic proofs: expand factorials and cancel common terms
- Combinatorial proofs: identify what each side counts, then argue they count the same set
- Why a combinatorial proof is not just "checking with numbers"
Skills
- Prove symmetry and Pascal's identity algebraically and combinatorially
- Prove the absorption identity algebraically
- Identify and apply identities to simplify combinatorial expressions
This identity says that choosing $r$ objects from $n$ is equivalent to choosing $n-r$ objects to leave out.
Algebraic proof:
Combinatorial proof: $\binom{n}{r}$ counts the number of ways to choose $r$ people from a group of $n$ to join a committee. Each such choice automatically determines the $n-r$ people who are not on the committee — and there are $\binom{n}{n-r}$ ways to make that complementary choice. Since each selection of $r$ people corresponds to exactly one selection of $n-r$ people to exclude, $\binom{n}{r} = \binom{n}{n-r}$. $\square$
Symmetry: n{r} = n{n-r} for all 0 r n; Algebraic: substitute the factorial formula, simplify — both give n!{r!(n-r)!}
Pause — copy the symmetry identity into your book: $\binom{n}{r} = \binom{n}{n-r}$; algebraic proof — substitute the factorial formula and cancel; both sides simplify to $\frac{n!}{r!(n-r)!}$.
Quick check: Using the symmetry identity, which of the following equals $\binom{8}{5}$?
We just saw the symmetry identity $\binom{n}{r} = \binom{n}{n-r}$ proved algebraically. That raises a question: Pascal's triangle adds adjacent entries to get the row below — is there a clean algebraic proof that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$? This card answers it → put both terms over the common denominator $(r+1)!(n-r)!$, factor the numerator, and recognise $(n+1)!$ on top.
Pascal's identity is the rule that generates every entry in Pascal's Triangle from the two entries above it.
Algebraic proof:
Combinatorial proof: Consider a group of $n+1$ people, one of whom is person $X$. We want to count $r+1$-person committees from this group — there are $\binom{n+1}{r+1}$ ways. Split into two cases: Case 1 — $X$ is not on the committee; then we choose all $r+1$ members from the remaining $n$ people: $\binom{n}{r+1}$ ways. Case 2 — $X$ is on the committee; then we choose the remaining $r$ members from the other $n$ people: $\binom{n}{r}$ ways. These cases are mutually exclusive and exhaustive, so $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$. $\square$
Pascal's identity: n{r} + n{r+1} = n+1{r+1}; Algebraic: put over common denominator (r+1)!(n-r)!, factor numerator, get (n+1)! on top
Pause — copy Pascal's identity into your book: $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$; algebraic derivation — use common denominator $(r+1)!(n-r)!$, factor numerator to get $(n+1)!$.
Did you get this? True or false: Pascal's identity states $\binom{n}{r-1} + \binom{n}{r} = \binom{n+1}{r}$.
Worked examples · 3 in a row, reveal as you go
Prove that $r\binom{n}{r} = n\binom{n-1}{r-1}$ algebraically.
Prove $\binom{n}{r} = \binom{n}{n-r}$ using a combinatorial argument.
Use Pascal's identity and the symmetry identity to simplify: $\binom{10}{4} + \binom{10}{5}$, and verify numerically.
Fill the gap: By Pascal's identity, $\binom{7}{2} + \binom{7}{3} = \binom{}{3}$, so the missing top number is .
Common misconceptions · the 3 traps that cost marks
Did you get this? True or false: showing that $\binom{6}{2} = \binom{6}{4} = 15$ is a valid proof that $\binom{n}{r} = \binom{n}{n-r}$ for all $n$ and $r$.
Activities · practice with the ideas
Use the symmetry identity to write an equivalent expression for $\binom{12}{9}$, and evaluate it.
Apply Pascal's identity to simplify $\binom{9}{3} + \binom{9}{4}$ without computing each term separately.
Prove algebraically that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$. Show all factorial steps.
Prove $r\binom{n}{r} = n\binom{n-1}{r-1}$ algebraically, then verify it numerically for $n = 5$, $r = 2$.
Give a combinatorial proof of Pascal's identity $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$. State your counting problem, explain each side, then conclude.
Odd one out: Which of the following is NOT a valid combinatorial identity?
Earlier you were asked: why are $\binom{6}{2}$ and $\binom{6}{4}$ equal?
The answer is the symmetry identity $\binom{n}{r} = \binom{n}{n-r}$. Choosing 2 people from 6 to be on a committee is equivalent to choosing the 4 people who are not on the committee — the same decision, made from opposite perspectives. Every time you choose 2 to include, you are simultaneously choosing 4 to exclude. Since the decisions are in one-to-one correspondence, the counts must be equal.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ algebraically. (3 marks)
Q2. Prove that $n \cdot \binom{n-1}{r-1} = r \cdot \binom{n}{r}$ algebraically. (2 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. $\binom{12}{9} = \binom{12}{3} = \frac{12 \times 11 \times 10}{6} = 220$. [2]
2. $\binom{9}{3} + \binom{9}{4} = \binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{24} = 210$. [2]
3–5. See the worked examples in section 07 above.
Q1 (3 marks): LHS $= \dfrac{n!}{r!(n-r)!} + \dfrac{n!}{(r+1)!(n-r-1)!}$ [0.5] $= \dfrac{n!(r+1) + n!(n-r)}{(r+1)!(n-r)!}$ [1] $= \dfrac{n!(n+1)}{(r+1)!(n-r)!} = \dfrac{(n+1)!}{(r+1)!(n-r)!} = \binom{n+1}{r+1}$ = RHS [1.5].
Q2 (2 marks): RHS $= r \cdot \dfrac{n!}{r!(n-r)!} = \dfrac{n!}{(r-1)!(n-r)!}$ [1]. LHS $= n \cdot \dfrac{(n-1)!}{(r-1)!(n-1-(r-1))!} = n \cdot \dfrac{(n-1)!}{(r-1)!(n-r)!} = \dfrac{n!}{(r-1)!(n-r)!}$ [1]. LHS = RHS. $\square$
Five timed questions. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering combinatorics questions. A lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.