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).
Start with the warm-up and record your first reasoning.
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?
Orient yourself to the lesson goals, language, and core approach.
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}$
Work through the concept and complete its check.
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:
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$:
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?
Build the next proof move and complete its check.
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}$:
$\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.
Follow the worked examples, then complete the check.
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)$ equals .
Correct the common traps and test your understanding.
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.
Complete the practice activities and revisit your opening thinking.
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.
Multiple choice, then short answer under exam conditions.
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)
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].
Sit the module quiz, then close the lesson off.
A full module quiz covering every lesson in this module, not just this one. Set aside a decent block of time and treat it like a real assessment.
Start the module quiz →Tick when you've finished the practice and review.
Work through this topic 1-on-1 with an experienced HSC tutor.
Book a free session →