Mathematical Induction · aiwiki.page

Mathematical induction is a method of mathematical proof used to establish statements about all natural numbers, or all integers above a specified starting value. It combines a proof of an initial case with a proof that each case implies the next. This finite argument establishes infinitely many instances. Despite its name, mathematical induction is deductive reasoning, not inductive reasoning based on observed examples: its conclusion follows necessarily once both proof obligations are satisfied. (cs.cornell.edu)

The induction principle

Let $P(n)$ be a statement depending on an integer $n$ , and let $n_0$ be the starting value. An induction proof has two essential parts:

Base case: prove $P(n_0)$ .
Inductive step: for an arbitrary integer $k\geq n_0$ , assume $P(k)$ and prove $P(k+1)$ .

The temporary assumption $P(k)$ is the induction hypothesis. Together, these parts establish

P(n)\quad\text{for every integer }n\geq n_0.

The starting value may be zero, one, or another integer, depending on the statement. The inductive step must apply to every eligible $k$ , rather than merely to selected examples. (cs.cornell.edu)

There is no circular assumption that the desired theorem already holds universally. Instead, the step establishes a conditional implication. The base case supplies its first antecedent; successive applications then establish every later case. In logic, the distinction between assuming $P(k)$ within a conditional argument and asserting $\forall n\,P(n)$ is fundamental. (cs.cornell.edu)

A worked example

An elementary identity in arithmetic is

1+2+\cdots+n=\frac{n(n+1)}2 \qquad(n\geq1).

Define $P(n)$ to be this equation. The base case $n=1$ holds because both sides equal one. For the inductive step, assume

1+2+\cdots+k=\frac{k(k+1)}2.

Adding $k+1$ , and using algebra, gives

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}2+(k+1)\\ &=\frac{(k+1)(k+2)}2. \end{aligned}

This is precisely $P(k+1)$ , so induction proves the identity for every positive integer. The hypothesis is used at the point where the first $k$ terms are replaced by their stated sum. (cs.cornell.edu)

Strong induction

Strong induction, also called complete induction, permits the step to assume every earlier case, rather than only the immediately preceding case. After establishing $P(n_0)$ , one proves $P(k+1)$ under the assumptions

P(n_0),P(n_0+1),\ldots,P(k).

Ordinary and strong induction are equivalent in proving power. To recover strong induction from ordinary induction, apply ordinary induction to the statement that all cases from $n_0$ through $n$ hold. The stronger hypothesis often makes a proof easier to organize. (cs.cornell.edu)

For example, every integer amount $n\geq12$ can be expressed as $4a+5b$ , where $a,b$ are nonnegative integers. The base cases are $12,13,14,15$ . For any $n\geq16$ , the earlier amount $n-4$ has such a representation; adding four gives one for $n$ . This example also shows why a proof may require several initial cases: the step must have an established earlier case available at every boundary. (cs.cornell.edu)

Foundations and well-ordering

Induction is part of the Peano axioms for natural-number arithmetic. In first-order logic, it appears as an axiom schema: each eligible formula supplies an induction axiom. With zero as the initial number and $S(n)$ denoting its successor, the schema has the form

\bigl(P(0)\land\forall n(P(n)\rightarrow P(S(n)))\bigr) \rightarrow\forall n\,P(n).

Thus induction is a foundational principle, not merely a shortcut for checking examples. (web.mit.edu)

In the usual classical setting, induction is equivalent to the well-ordering principle for natural numbers: every nonempty subset has a least element. If an induction argument had counterexamples, choose the least one. It cannot be the base case; its predecessor therefore satisfies the statement, and the inductive step forces the counterexample to satisfy it too. This proof by contradiction explains the least-counterexample formulation of induction. (people.math.sc.edu)

Structural induction and computation

Structural induction extends the method to inductively generated objects, including finite lists, trees, and expressions. One proves the property for the basic objects and shows that every construction rule preserves it when the component objects possess it. Ordinary induction is the instance in which objects are generated from zero by repeated application of the successor operation. (cs.cornell.edu)

In computer science, induction is closely related to recursion. A recursive algorithm reduces a task to smaller instances; an induction proof establishes correctness by assuming those smaller computations behave as specified. Structural induction similarly follows the construction of a data structure. Strong induction is also useful in proving computational complexity bounds when a running-time recurrence involves several smaller input sizes. (cs.cornell.edu)

Common errors

Checking many cases does not replace an inductive step. Conversely, proving the step without an initial case establishes only a conditional chain, with no starting point. A valid argument must also cover the smallest transition required by its stated range. (cs.cornell.edu)

The familiar false proof that all horses have the same color illustrates this boundary error. It compares two groups of $k$ horses within a group of $k+1$ , using their overlap to connect their colors. For $k=1$ , however, the groups do not overlap. The step therefore fails exactly where it must establish the two-horse case from the one-horse case. (ocw.mit.edu)