Proof by Induction

Proof by induction is the tool that lets you reason about all natural numbers at once — 0, 1, 2, 3, and so on, without ever reaching the end. It unlocks the deepest ideas in computer science: you will use it to prove that algorithms actually work (correctness proofs for sorting, searching, and graph traversal), to understand recursion (where a function calls itself, and induction is the proof that it stops), and to reason about data structures like trees and heaps. When you later study loop invariants — the property that stays true every time a loop runs — induction is the underlying logic. Without induction, you can test a program on ten inputs and hope; with induction, you know it works for every input. This page teaches you the method, and the neighbouring topics in your library — Catalan Numbers, Integer Partitions, Modular Arithmetic — all rely on it.

Imagine you want to prove that a statement is true for every natural number: 0, 1, 2, 3, ... and so on forever. You can't check them all one by one, because there are infinitely many. Induction gives you a two-step trick. First, you check the smallest case (the base case). Second, you show that if the statement is true for some number, then it must be true for the next number. Once you have those two things, you can start at the base case and walk up: true for 0 forces true for 1, which forces true for 2, which forces true for 3, and so on — like a chain of falling dominoes. If you've set up the chain correctly, every domino falls, even though you never touched them all. The magic is that you don't need to write out the infinite chain; the 'if-then' step covers every link at once. The real work is in that second step — the inductive step — where you assume the statement is true for one number (the assumption is called the 'inductive hypothesis') and then prove it for the next number. It's like proving a recipe works for any portion size by showing that if it works for one portion, it works for two, and so on.

Think of a staircase that goes up forever. You want to prove that you can reach any step. You can't climb them all right now. Instead, you do two things: first, you step onto the first stair (the base case, say step 0). Second, you prove that if you are standing on any stair, you can always take one more step to reach the next stair (the inductive step). Once you've done that, you can be certain that you can reach stair 100, stair 1000, stair 10,000 — because you can start at 0, step to 1, step to 2, and so on. The 'if I'm on one stair, I can reach the next' is a general rule that covers all stairs at once. But here's where the analogy stops: in real life, you might get tired or the stairs might crumble, so the rule 'if I'm on a stair, I can step to the next' might break for some stair. In induction, that rule has to be proven for every single stair without exception — you can't just say 'it works for the ones I've tried'. Also, the staircase analogy suggests a physical process of climbing, but induction is a logical proof, not a physical act. You don't actually move; you just show that the chain of reasoning is sound. Another place the analogy breaks: in induction, the base case might not be 0; sometimes it's 1 or 2, and you have to be careful to start at the right place.

Proof by induction is a method of proving a statement is true for every natural number by establishing a base case (the statement holds for the smallest number, often 0 or 1) and then showing that if the statement is true for any number n, it must also be true for n+1.

This sits at the heart of Discrete Mathematics, which your library records as the mathematics of countable structures — logic, sets, relations, functions, combinatorics, and proof technique. Induction is the proof technique. It connects directly to recursion, which you will meet in algorithms: induction is the proof version, recursion is the computation version. The book in your library, 'Foundations of Algorithmic Thinking', says 'Induction and recursion are the same idea in two domains — one proves, the other computes.' That is the key bridge. Neighbouring topics: Catalan Numbers are defined by a recurrence that is proved by induction; Integer Partitions use induction to establish counting formulas; Modular Arithmetic uses induction to prove properties of powers and congruences. Also, loop invariants, which you'll study later, are proven using induction over the number of loop iterations. So this concept is the glue.