Induction for Combinatorial Identities
How many subsets does a set of $n$ elements have? Exactly $2^n$ — and induction proves it in a few elegant lines using Pascal's identity. In this lesson you'll master how $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$ powers the inductive step for binomial coefficient identities.
Count the number of subsets of a set for small values of $n$: try $n = 0, 1, 2, 3$. What pattern do you see? Can you predict the count for $n = 4$ before checking?
Combinatorial induction always comes down to two key moves: split the $(k+1)$ sum into boundary terms and an inner sum, then apply Pascal's identity to convert $\binom{k+1}{r}$ back into two $\binom{k}{\cdot}$ terms, and finally use the inductive hypothesis.
Pascal's identity connects adjacent rows of Pascal's triangle:
$\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}$
Reading backwards: $\binom{k+1}{r} = \binom{k}{r} + \binom{k}{r-1}$. This is how you break row $k+1$ into row $k$ pieces.
Key facts
- Pascal's identity: $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$
- $\sum_{r=0}^{n}\binom{n}{r} = 2^n$ (total subsets of an $n$-element set)
- Absorption identity: $r\binom{n}{r} = n\binom{n-1}{r-1}$
Concepts
- How Pascal's identity connects row $k$ to row $k+1$ of Pascal's triangle
- Why boundary terms $\binom{n}{0}$ and $\binom{n}{n}$ must be separated before applying Pascal's identity
- How index substitution ($s = r-1$) realigns summation limits
Skills
- Prove $\sum_{r=0}^{n}\binom{n}{r}=2^n$ by induction using Pascal's identity
- Prove $\sum_{r=0}^{n}(-1)^r\binom{n}{r}=0$ for $n\geq1$ by induction
- Handle index shifts and boundary terms correctly in the inductive step
The cornerstone of binomial induction is Pascal's identity:
This lets us relate row $n$ of Pascal's triangle to row $n+1$, which is exactly what we need for the inductive step. Reading it in reverse: to express $\binom{k+1}{r}$ in terms of row-$k$ coefficients, we split it as $\binom{k}{r}+\binom{k}{r-1}$.
When we sum $\binom{k+1}{r}$ over $r$ from 1 to $k$, each term splits into two row-$k$ terms. After re-indexing the second group ($s=r-1$), both inner sums become $\sum_{r=0}^{k}\binom{k}{r}$, which equals $2^k$ by the inductive hypothesis.
The cornerstone of binomial induction is Pascal's identity :
Pause — copy Pascal's identity $\binom{k}{r-1}+\binom{k}{r}=\binom{k+1}{r}$ and explain why it holds: choosing $r$ items from $k+1$ either includes or excludes the new item into your book.
Quick check: Which identity lets you express $\binom{k+1}{r}$ as a sum of two row-$k$ binomial coefficients in the inductive step?
We just saw Pascal's identity $\binom{k}{r-1}+\binom{k}{r}=\binom{k+1}{r}$, which rewrites any row-$(k+1)$ term using row-$k$ terms. That raises a question: how does applying this to $\sum_{r=0}^{k+1}\binom{k+1}{r}$ and using the hypothesis $\sum_{r=0}^k\binom{k}{r}=2^k$ give the required $2^{k+1}$? This card answers it → the split sum equals $2\cdot\sum_{r=0}^k\binom{k}{r}=2\cdot2^k=2^{k+1}$.
Statement: Prove by induction that $\displaystyle\sum_{r=0}^{n}\binom{n}{r} = 2^n$ for all non-negative integers $n$.
Step 1 — Base Case ($n = 0$):
LHS $= \binom{0}{0} = 1$; RHS $= 2^0 = 1$. LHS = RHS. True for $n = 0$.
Step 2 — Inductive Hypothesis:
Assume $\displaystyle\sum_{r=0}^{k}\binom{k}{r} = 2^k$ for some $k \geq 0$.
Step 3 — Inductive Step ($n = k + 1$):
Apply Pascal's identity to the inner sum: $\binom{k+1}{r} = \binom{k}{r}+\binom{k}{r-1}$
Split and re-index the second group ($s = r-1$, so $s$ runs from $0$ to $k-1$):
True for $n = k+1$. By the principle of mathematical induction, true for all $n \geq 0$. ∎
Statement: Prove by induction that $\displaystyle\sum_{r=0}^{n}\binom{n}{r} = 2^n$ for all non-negative integers $n$.
Pause — copy the induction proof that $\sum_{r=0}^n\binom{n}{r}=2^n$, highlighting how the Pascal split converts the $k+1$ sum into $2\times2^k$ into your book.
Did you get this? True or false: in the proof of $\sum_{r=0}^{n}\binom{n}{r}=2^n$, we separate the terms $\binom{k+1}{0}$ and $\binom{k+1}{k+1}$ so that Pascal's identity can be applied cleanly to the remaining inner terms.
Worked examples · 3 in a row, reveal as you go
Prove by induction that $\displaystyle\sum_{r=0}^{n}(-1)^r\binom{n}{r} = 0$ for all integers $n \geq 1$.
Prove by induction that $\displaystyle\sum_{r=0}^{n}r\binom{n}{r} = n2^{n-1}$ for all positive integers $n$.
Verify Pascal's identity $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$ algebraically (using the formula for $\binom{n}{r}$), for general $n$ and $1 \leq r \leq n$.
Fill the gap: By the inductive hypothesis, $\displaystyle\sum_{r=0}^{k}\binom{k}{r} = $. Doubling this gives $2^{k+1}$, completing the inductive step for $\sum\binom{n}{r}=2^n$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: when re-indexing with $s = r - 1$, a sum $\sum_{r=1}^{k}$ becomes $\sum_{s=0}^{k-1}$.
Activities · practice with the ideas
State Pascal's identity from memory. Then verify it numerically for $n=4$, $r=2$.
In the inductive step for $\sum\binom{n}{r}=2^n$, after separating boundary terms, write out the sum $\sum_{r=1}^{k}\binom{k+1}{r}$ with Pascal's identity applied. Do not simplify yet.
Prove by induction that $\displaystyle\sum_{r=0}^{n}\binom{n}{r} = 2^n$ for all $n \geq 0$ in full exam style.
Verify the alternating sum identity $\sum_{r=0}^{n}(-1)^r\binom{n}{r}=0$ for $n=3$ directly (expand all terms).
Explain in one sentence why $\binom{k+1}{0}$ and $\binom{k+1}{k+1}$ must be separated from the inner sum before applying Pascal's identity.
Odd one out: Three of these statements about combinatorial induction proofs are true. Which one is FALSE?
Earlier you counted subsets for small $n$: 1, 2, 4, 8. That pattern is $2^n$.
The induction proof captures why: when you add a new element to a set of size $k$, every existing subset either excludes the new element (the original $2^k$ subsets) or includes it (another $2^k$ subsets). So the count doubles: $2^k + 2^k = 2^{k+1}$. Pascal's identity makes that same doubling argument work in algebraic form for the binomial coefficient sum.
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. State Pascal's identity and verify it for $n=5$, $r=3$. (1 mark)
Q2. Prove by induction that $\displaystyle\sum_{r=0}^{n}\binom{n}{r} = 2^n$ for all non-negative integers $n$. (3 marks)
Q3. Prove by induction that $\displaystyle\sum_{r=0}^{n}(-1)^r\binom{n}{r} = 0$ for all integers $n \geq 1$. (3 marks)
Comprehensive answers (click to reveal)
Q1 (1 mark): Pascal: $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$. Verify: $\binom{5}{3}+\binom{5}{2}=10+10=20=\binom{6}{3}$. [1]
Q2 (3 marks): Base $n=0$: $\binom{0}{0}=1=2^0$ [1]. IH: $\sum_{r=0}^{k}\binom{k}{r}=2^k$. Step: separate boundary terms, apply Pascal to inner sum, re-index to get $\sum_{r=0}^{k}\binom{k}{r}+\sum_{r=0}^{k}\binom{k}{r}=2\cdot2^k=2^{k+1}$ [1]. Conclusion [1].
Q3 (3 marks): Base $n=1$: $1-1=0$ [1]. IH: $\sum_{r=0}^{k}(-1)^r\binom{k}{r}=0$. Step: apply Pascal to each $\binom{k+1}{r}$, split into two sums both equal to 0 by IH (or equal and opposite), giving total 0 [1]. Conclusion [1].
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 combinatorial induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.