Mathematical Induction Explained

Intro to Proofs · Axiom Academy

A powerful proof technique: establish a base case, prove the inductive step, and conclude truth for all natural numbers. 1. The Principle of Mathematical Induction To prove P(n) is true for all , we need just two things: a base case and an inductive step . Together they force the statement to hold for every natural number. Base case: prove the statement for n = 1 Inductive step: if it holds at k , it holds at k+1 If both conditions hold, we conclude that P(n) is true for all natural numbers . This is the Principle of Mathematical Induction , a fundamental axiom that defines the structure of the natural numbers. Picture infinitely many dominoes in a row, numbered Each domino represents a statement P(n) . To knock them all down, you need: The first domino falls → base case: P(1) is true. Each domino knocks over the next → inductive step: . A classic statement to prove this way is the sum of the first n whole numbers. Watch the dominoes fall one by one as the running total snaps to the closed form at every step. A proof by induction always follows this template — a chain of implications anchored by the base case: The base case proves P(1) outright. The inductive step is a single reusable argument: it forges every link at once. Following the links from P(1) reaches P(2) , then P(3) , and so on to every P(n) . 4. Why This Isn't Circular Reasoning A common misconception: "Isn't assuming P(k) to prove P(k+1) circular reasoning?"

This is the written version of the interactive lesson above. See the full Intro to Proofs course.