Discrete Mathematics — Logic & Number Theory
Proof by pattern — induction
continues from lesson 3 — values defined earlier in the course stay live here
ELI5: induction is the domino effect: show the first domino falls, and show each domino knocks over the next, and all of them fall. A classic result it proves: the sum of the first n odd numbers is exactly n² (1 = 1, 1+3 = 4, 1+3+5 = 9, …).
= 1 + 3 + 5 + ⋯ + 13 (seven odds)
✓ pass the first 7 odd numbers sum to 7² = 49
Real-world hook: induction is how we prove an algorithm is correct for every input size, not just the ones we tested — the bedrock of trustworthy software.
Try it yourself: what do the first 10 odd numbers (1 + 3 + ⋯ + 19) add up to? (The pattern says n².)
✏️ Your turn: the first 10 odd numbers sum to 10². The check compares against actually adding them up.
✓ pass green when your total matches the brute-force sum
Where next: Multivariable Calculus takes the derivative into three dimensions.