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 confidencethat 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.