The domino principle
Induction is how you prove something about ALL counting numbers without checking them one by one (which would take forever). You show two things: the claim is true at the start (0 or 1), and truth is contagious — if it holds for some number, it must hold for the next. Those two facts together sweep through every number there is.
A line of dominoes stretching to the horizon. Tip the first one, make sure each domino is close enough to knock over the next, and you know — without watching — that domino one million falls too.
Claim: 1 + 2 + ... + n = n(n+1)/2. Start: for n=1, both sides are 1. Step: if it holds for n, add (n+1) to both sides and the formula for n+1 pops out. Done — true for every n.
Induction is the engine behind almost every fact about whole numbers, and it is how computer scientists prove that loops and recursive programs are correct.
Level 1 The precise statement
For any property P of natural numbers: if P(0) holds and P(n) implies P(n+1) for every n, then P(n) holds for all n.
Level 3 What it stands on (0 direct)
Nothing — this is foundational. It is one of the roots of the graph.
Level 4 The verified record
This page is generated from a machine-checked node. The kernel confirms its dependencies resolve, nothing is circular, and it grounds in axioms (foundation: peano). The content hash below makes tampering evident.
2 downstream results would collapse with it. See the blast radius on the graph →