A ladder metaphor explains how finite reasoning proves infinitely many cases
If you can step onto the bottom rung of a ladder, and from any rung you can always reach the next, you can climb as high as you like. That is mathematical induction: two short arguments that together settle a statement for every natural number, a technique traced back to al-Karaji around 1000 AD.
An induction proof has two parts. The base case shows the statement holds for a starting value, usually 0 or 1 depending on where an author begins the natural numbers, though any fixed number will do. The induction step assumes the statement for some arbitrary n, the so-called induction hypothesis, and shows it must then hold for n plus 1. Falling dominoes are the other favourite image. A classic exercise uses it to show that adding 0 through n gives n times n plus 1, over two.
The name misleads. Philosophical induction draws a probable conclusion from many observed cases, while the mathematical version is a strictly deductive argument whose variable ranges over infinitely many values, so it yields certainty rather than likelihood. Extended to well-founded structures such as trees, it becomes structural induction, closely tied to recursion and underlying most proofs that computer programs are correct.
Its early history is disputed. David E. Joyce finds no sign of it in Euclid, and Fabio Acerbi's claim in 2000 of an implicit version in Plato's Parmenides was rejected in 2021 by Negrepontis and Farmaki. Al-Karaji applied an inductive argument to arithmetic sequences, proving the binomial theorem, facts about Pascal's triangle and a formula for summing cubes already known to Aryabhata. He worked with the specific number 10 and reasoned downward to 1, but his method was built to generalise. His original text is lost and survives through al-Samawal al-Maghribi's algebra treatise of around 1150. In India, Bhaskara's cyclic method contains similar implicit proofs.
Gersonides, who lived from 1288 to 1344, gave the earliest rigorous use. Francesco Maurolico in 1575 showed that the first n odd numbers add up to n squared. Blaise Pascal stated the principle explicitly in his 1665 treatise on the arithmetic triangle, Pierre de Fermat relied on the related method of infinite descent, and Jakob Bernoulli made it widely known. A formal footing came in the 19th century through Boole, De Morgan, Peirce, Peano and Dedekind.
Source: Mathematical induction
