Mathematical induction

A proof method for statements about natural numbers: prove an initial case, then prove that each case implies the next.

Base case: The initial instance established directly in an inductive proof. It anchors the chain of implications at the starting natural number.
Natural number: An element of the counting-number system, whose inclusion of zero depends on convention. The cases covered by induction are indexed by natural numbers.
Recursive definition: A definition that specifies initial values and rules for generating later values from earlier ones. Induction often proves properties of objects defined by the same base-and-step pattern.
Structural induction: A proof method that establishes a property for recursively constructed objects from their construction rules. It generalizes the base-and-step pattern from natural-number indices to recursive structures.
Inductive step: An argument that a statement for one index implies it for the next index. It propagates truth from each case to its successor.
Proposition: A declarative statement that is either true or false. Induction proves a proposition separately indexed by each natural number.
Recurrence relation: An equation defining terms of a sequence using one or more earlier terms. Induction verifies formulas and bounds for recursively generated sequences.
Infinite descent: A proof technique showing that a supposed counterexample would produce an indefinitely decreasing sequence of positive integers. It often proves impossibility by reversing induction's forward progression.
Induction hypothesis: The assumption that a statement holds at a specified stage, used to prove a later stage. It supplies the temporary premise used in the inductive step.
Logical implication: A relation between statements that is false only when its premise is true and its conclusion false. The inductive step is an implication from one indexed proposition to the next.

Linked from 54 pages