Geometric & Combinatorial Induction
A topologist counts the diagonals of a 100-sided polygon. A network engineer counts the handshakes in a room of 50 conference attendees. Both reach for the same tool — mathematical induction applied to a counting argument. In this lesson you'll extend induction beyond algebraic sums and divisibility to prove geometric formulas (interior angles, diagonals) and combinatorial identities (handshake counting, subset totals).
You already know induction works on algebraic sums like $\sum_{k=1}^n k = \tfrac{n(n+1)}{2}$. Before reading on — sketch a triangle, a quadrilateral and a pentagon, and write down the sum of interior angles you remember for each. What pattern do you see? Could you imagine proving it by induction?
Geometric and counting proofs reward two habits: interpret what "+1" means visually (one more vertex, one more guest, one more region), then describe the extra contribution exactly before writing equations. The inductive step always reduces a $k+1$ configuration to a $k$ configuration plus a known increment.
The add-one-and-account strategy: (1) take the $(k+1)$-case configuration, (2) remove one element (vertex / person / region) to reveal a $k$-case, (3) count exactly what the removed element contributed and add it back.
Interior angles: $S(n) = 180(n-2)°$ · Handshakes: $H(n) = \tfrac{n(n-1)}{2}$
Key facts
- Sum of interior angles of an $n$-gon: $S(n) = 180(n-2)°$
- Number of handshakes among $n$ people: $H(n) = \tfrac{n(n-1)}{2}$
- Subset identity: $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$
Concepts
- Why the inductive step is naturally a "one more element" geometric move
- How combinatorial identities can be proved either algebraically or by double counting
- Why tilings and colourings require careful base cases and well-defined increments
Skills
- Prove geometric formulas (interior angles, diagonals, region counts) by induction
- Prove combinatorial identities such as $\sum\binom{n}{k}=2^n$ by induction
- Apply induction to tiling and colouring problems with rigorous base cases
The classic geometric induction is the interior-angle sum of a convex polygon. Claim: $S(n) = 180(n-2)°$ for $n \geq 3$. The four-step structure never fails:
- Base. $n=3$: a triangle has interior-angle sum $180°$, and $180(3-2)=180$. ✓
- Hypothesis. Assume the claim for $n=k$: any convex $k$-gon has angle sum $180(k-2)°$.
- Step. Take a convex $(k+1)$-gon. Draw a diagonal from one vertex to a non-adjacent vertex, splitting it into a $k$-gon and a triangle.
- Conclude. By hypothesis the $k$-gon contributes $180(k-2)°$; the triangle contributes $180°$. Total: $180(k-2) + 180 = 180(k-1) = 180((k+1)-2)°$. ✓
Hook revisited (handshakes). For $n=12$ people the count is $\binom{12}{2} = \tfrac{12 \cdot 11}{2} = 66$. To prove $H(n) = \tfrac{n(n-1)}{2}$ for all $n \geq 2$:
- Base: $n=2$, one handshake, and $\tfrac{2 \cdot 1}{2}=1$. ✓
- Step: assume $H(k) = \tfrac{k(k-1)}{2}$. When a $(k+1)$-th guest arrives, they shake hands with each of the existing $k$ people — adding $k$ new handshakes.
- So $H(k+1) = \tfrac{k(k-1)}{2} + k = \tfrac{k(k-1)+2k}{2} = \tfrac{k(k+1)}{2} = \tfrac{(k+1)((k+1)-1)}{2}$. ✓
Interior-angle sum: $S(n) = 180(n-2)°$ for $n \geq 3$; base $n=3$ gives $180°$ ✓ · Inductive step for polygons: split $(k+1)$-gon by a diagonal into a $k$-gon + triangle · Handshakes: $H(n) = \tfrac{n(n-1)}{2}$; each new guest adds $k$ handshakes · General principle: "+1" must be interpreted geometrically/combinatorially, not just algebraically
Pause — copy the interior-angle sum $S(n) = 180(n-2)°$, the diagonal-split inductive step, and the handshake formula $H(n) = n(n-1)/2$ into your book.
Quick check: A convex hexagon ($n=6$) has interior-angle sum equal to which value?
We just saw that the interior angle sum $S(n) = 180(n-2)°$ is proved inductively by splitting a $(k+1)$-gon with a diagonal into a $k$-gon and a triangle. That raises a question: can induction prove identities about binomial coefficients? This card answers it → $\sum_{k=0}^n \binom{n}{k} = 2^n$ via Pascal's identity $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$, which doubles the inductive sum.
One of the most useful combinatorial facts: the total number of subsets of an $n$-element set is $2^n$. Equivalently, $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$. Here is the induction proof using Pascal's identity $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$:
- Base. $n=0$: $\binom{0}{0} = 1 = 2^0$. ✓
- Step. Assume $\sum_{k=0}^{n}\binom{n}{k} = 2^n$. Consider $\sum_{k=0}^{n+1}\binom{n+1}{k}$.
- By Pascal's identity each middle term $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$, and the endpoints satisfy $\binom{n+1}{0}=\binom{n}{0}$ and $\binom{n+1}{n+1}=\binom{n}{n}$.
- Summing telescopes each term of $\binom{n}{\cdot}$ into the new sum twice, giving $2\sum_{k=0}^{n}\binom{n}{k} = 2 \cdot 2^n = 2^{n+1}$. ✓
$\sum_{k=0}^{n}\binom{n}{k} = 2^n$ — total subsets of $\{1, \ldots, n\}$ · Pascal's identity: $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ · Induction step: each Pascal split contributes the previous sum twice, doubling $2^n \to 2^{n+1}$ · Double count: each element is in or out — $2^n$ subsets directly
Pause — copy $\sum_{k=0}^n \binom{n}{k} = 2^n$, Pascal's identity $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$, and the step argument that each Pascal split doubles $2^n$ to $2^{n+1}$ into your book.
Did you get this? True or false: the inductive step for $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ uses Pascal's identity to rewrite each $\binom{n+1}{k}$ as a sum of two consecutive $\binom{n}{\cdot}$ terms.
Worked examples · 3 in a row, reveal as you go
Prove by induction that the interior-angle sum of a convex $n$-gon is $S(n) = 180(n-2)°$ for all integers $n \geq 3$.
Prove by induction that a convex $n$-gon has exactly $D(n) = \tfrac{n(n-3)}{2}$ diagonals for all integers $n \geq 3$.
Prove by induction that $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ for all integers $n \geq 0$.
Fill the gap: When a $(k+1)$-th guest joins a party where everyone has already shaken hands, the new guest shakes hands with exactly $k$ existing guests, so $H(k+1) = H(k) + $.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: when proving the handshake formula $H(n) = \tfrac{n(n-1)}{2}$ by induction, the appropriate base case is $n=1$ because a single person cannot shake hands.
Activities · practice with the ideas
Prove by induction that the interior-angle sum of a convex $n$-gon is $180(n-2)°$ for $n \geq 3$. Write the full proof with base, hypothesis and step.
Prove by induction that $n$ people shaking hands pairwise gives $\tfrac{n(n-1)}{2}$ handshakes for $n \geq 2$.
Prove by induction that a convex $n$-gon has $\tfrac{n(n-3)}{2}$ diagonals for $n \geq 3$. Explain carefully what the new vertex contributes.
Prove by induction that $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n$ for $n \geq 0$. Use Pascal's identity in the inductive step.
A $2^n \times 2^n$ square grid with one square removed can always be tiled by L-shaped trominoes (each covering 3 unit squares). State the base case and outline the inductive step (you do not need a full proof).
Odd one out: Three of these statements about geometric/combinatorial induction are correct. Which one is NOT?
Earlier you predicted the handshake total for $n=12$ people.
The answer is $\tfrac{12 \cdot 11}{2} = 66$. The inductive step is: when a new guest arrives, they shake hands with all $k$ existing guests, so $H(k+1) = H(k) + k$. The same pattern — describe what the new element contributes — works for polygon angle sums, diagonal counts, and subset identities. Geometric and combinatorial induction is induction with a story.
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. Use induction to prove that the interior-angle sum of a convex $n$-gon is $180(n-2)°$ for $n \geq 3$. (2 marks)
Q2. Use induction to prove that the number of handshakes among $n$ people (each pair shaking hands exactly once) is $\tfrac{n(n-1)}{2}$ for $n \geq 2$. (3 marks)
Q3. Prove by induction that $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ for all integers $n \geq 0$. State Pascal's identity if used. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Base $n=3$: triangle = $180° = 180(3-2)$ ✓. Hypothesis: $S(k)=180(k-2)°$. Step: split a convex $(k+1)$-gon by a diagonal into a $k$-gon + triangle: $S(k+1) = 180(k-2)+180 = 180(k-1) = 180((k+1)-2)$. By induction true for all $n \geq 3$.
2. Base $n=2$: 1 = $\tfrac{2 \cdot 1}{2}$ ✓. Hypothesis: $H(k)=\tfrac{k(k-1)}{2}$. Step: new guest adds $k$ handshakes, $H(k+1) = \tfrac{k(k-1)}{2} + k = \tfrac{k(k+1)}{2}$. By induction true for all $n \geq 2$.
3. Base $n=3$: 0 = $\tfrac{3 \cdot 0}{2}$ ✓. Hypothesis: $D(k)=\tfrac{k(k-3)}{2}$. Step: new vertex adds $k-2$ new diagonals plus reclassifies one side, so $D(k+1) = \tfrac{k(k-3)}{2} + (k-2) + 1 = \tfrac{(k+1)(k-2)}{2}$. By induction true for all $n \geq 3$.
4. Base $n=0$: $\binom{0}{0}=1=2^0$ ✓. Hypothesis: $\sum_{k=0}^n\binom{n}{k}=2^n$. Step: use Pascal on each $\binom{n+1}{k}$ to give $2\sum_{k=0}^n\binom{n}{k}=2 \cdot 2^n = 2^{n+1}$.
5. Base $n=1$: a $2 \times 2$ grid minus one square IS an L-tromino. Step: split a $2^{k+1} \times 2^{k+1}$ grid into four $2^k \times 2^k$ quadrants; place one tromino at the centre so each remaining quadrant has one missing square; apply the hypothesis to each quadrant.
Q1 (2 marks): Base $n=3$ shows $S(3)=180°$ [1]. Inductive step using diagonal split: $S(k+1)=S(k)+180°=180(k-1)°$ [1].
Q2 (3 marks): Base $n=2$: 1 handshake [1]. Inductive step: new guest contributes $k$ handshakes [1]; algebra to $\tfrac{(k+1)k}{2}$ [1].
Q3 (3 marks): Base $n=0$: $\binom{0}{0}=1=2^0$ [1]. Apply Pascal to expand $\binom{n+1}{k}$ [1]; sum telescopes to $2 \cdot 2^n = 2^{n+1}$ [1].
Five timed questions combining geometric and combinatorial induction. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.