Mathematical proof

A mathematical proof is a finite deductive argument from stated assumptions to a conclusion. It explains why the conclusion follows for every instance covered by its hypotheses. An informal mathematical proof can omit routine detail while making its assumptions and deductions clear; a formal proof expresses them in a specified formal language with specified inference rules. The distinction between assumptions, propositions, and deductions is introduced in Leighton and Rubinfeld, What is a proof?, sections 1–3.

Checking examples can suggest a pattern, but need not establish a universally quantified claim. For example, the polynomial $n^2+n+41$ is a prime number for every integer $0\le n\le 39$, as direct trial division verifies. At $n=40$ it equals $1681=41^2$, a composite number. Those first forty successes do not prove the claim for all natural numbers; one counterexample disproves it. The point is not to discard computation: it can find a conjecture, detect a mistake, or verify a finite exhaustive case analysis. The question is whether the cases checked cover the statement being claimed.

For a positive example, the sum of two even integers is even: writing them as $2a$ and $2b$ with $a,b\in \mathbb{Z}$ gives $2a+2b=2(a+b)$, and $a+b$ is an integer. This direct argument handles every allowed pair at once. A useful mathematical proof therefore does more than certify an answer: it exposes the mechanism and the exact assumptions that make the answer transferable.

Prove equality of expressions through a chain of substitutions justified by definitions, previously established equalities, or algebraic laws. Each step preserves the expression's value. In a programming language with lazy evaluation, an asserted program law must also preserve termination and the demanded amount of a partial value, not just agree on finite defined inputs.

A reductio rejects an assumption by deriving an absurd or contradictory consequence from it. In a classical mathematical proof of $P$, assume its negation and derive a contradiction. Constructively the same argument yields the double negation of $P$; removing it requires an additional logical principle. This differs from proving a negation directly by deriving a contradiction from the positive assumption.

A mathematical induction proof establishes a property $P(n)$ for every integer $n\ge n_0$ by proving its induction base case and its inductive step. If a counterexample existed, the well-ordering principle would give a least one; its predecessor and the inductive implication exclude it. The starting case excludes a counterexample at $n_0$.

The useful idea is to cover infinitely many cases with two finite pieces of reasoning. The induction base case starts the chain, and the inductive step shows that success at an arbitrary stage propagates to the next. It is especially natural when a construction adds one item at a time: another row of a diagram, another input processed by an algorithm, or another term of a sequence. The loop invariant method is the same propagation idea applied to successive stages of a computation.

For the triangular number $T_n=1+2+\cdots +n$, the proposed formula is $T_n=n(n+1)/2$. At $n=1$, both sides are one. Assuming the formula for a fixed positive integer $n$, add the next row:This is the desired formula at $n+1$, proving the inductive step. For example, $T_5=15$ and $T_6=15+6=21$; these numerical cases illustrate the general step rather than replace it.

The second picture explains where the formula comes from: two copies of the triangular arrangement tile an $n$ by $n+1$ rectangle. Thus $2T_n=n(n+1)$. The mathematical induction argument certifies how the formula continues, while the rearrangement makes its factors visible. Neither picture is restricted to the five rows drawn: both constructions are specified for every positive integer $n$.

Given an initial value $a$ and a specified successor rule on a set, there is a unique function on the natural numbers with that initial value and successor rule. Finite compatible approximations give existence; induction gives agreement of any two approximations and uniqueness. Recursive definitions of addition and multiplication apply this theorem with the other argument fixed.

Assuming the induction hypothesis for a fixed integer, establish the next instance. Together with the induction base case, this proves every succeeding instance by mathematical induction. The hypothesis is conditional within this argument, rather than an unsupported assumption that the desired theorem is already true.

The starting instance of a mathematical induction proof, established directly before the inductive step is applied. The implication $P(n)\Rightarrow P(n+1)$ alone can be true when every instance is false. For example, ${\sum }_{j=1}^{n}j=n(n+1)/2+C$ with $C\ne 0$ has a formally correct successor calculation but a false base case.

The assertion assumed for earlier cases during an induction proof. It is a conditional assumption inside the induction step, not an assumption that all cases already hold.

Strong induction establishes a proposition $P(n)$ for all integers $n\ge n_0$. Prove $P(n_0)$; then, for each $n\ge n_0$, assume every $P(k)$ with $n_0\le k\le n$ and prove $P(n+1)$. The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use $P(n+1)$ itself.^[ref]

This is useful when a construction breaks into smaller pieces of varying sizes. A prime factorization splits a composite number into smaller integer divisors, which need not be one less than the original integer. A recursive procedure can likewise call itself on several smaller inputs. The available cases should match those dependencies. Strong induction lets the mathematical proof follow the construction rather than forcing every step through the immediately preceding size.

Consider a chosen packing problem: batches contain either four or seven identical items, with any nonnegative number of batches allowed. Which integer totals can be formed? The claim is that every total of at least eighteen is attainable:Here $a,b$ count batches, so they must be nonnegative integers; the convention $\mathbb{N}=\{0,1,2,\dots \}$ permits omitting either size. Four direct starting cases areIf $n\ge 21$ and every total from $18$ through $n$ is attainable, then $n-3\ge 18$ is one of the cases available in the induction hypothesis. Add a batch of four to its representation to obtain $n+1$. Thus the inductive step applies to every new total from $22$ onward. Formally, one can start the strong induction at $18$ and handle the next three totals directly before using the uniform step. The finite checks and the propagation together establish all totals, not merely those drawn below.

Checking only $18$ and repeatedly adding four would reach only totals congruent to $18$ in modular arithmetic modulo four. The four induction base cases supply all four residue classes. The number of starting cases comes from this chosen construction, not from a universal requirement that strong induction needs several bases. A different construction can need different starting information.

The threshold is sharp for these batch sizes. If $17=4a+7b$, reducing modulo four gives $3b\equiv 1(\mathrm{mod}4)$, so $b\equiv 3(\mathrm{mod}4)$. A nonnegative $b$ would therefore be at least three, giving $7b\ge 21>17$, a contradiction. A finite failed search alone would need an explicit bound on $a,b$; this short modular arithmetic argument supplies a general obstruction.

Every integer $n\ge 2$ has a prime factorization. The induction base case $2$ is prime. For a larger integer, either it is prime or it is $ab$, with $2\le a,b<n$. The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for $n$. This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.^[ref]

For the chosen number $84$, one possible recursive decomposition isThe step at $84$ needs results for $6$ and $14$, rather than a result for $83$. Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.

The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.

Strong induction does not prove more than ordinary mathematical induction. Put $Q(n)={\bigwedge }_{k=n_0}^{n}P(k)$. Ordinary mathematical induction on $Q$ retains the earlier cases and obtains the next one, establishing the same conclusion. Conversely, an ordinary inductive step can ignore the extra cases allowed in a strong induction hypothesis.^[ref]

The well-ordering principle gives another view. A least counterexample would have all smaller cases true, so the strong induction step would establish that allegedly false case. The starting case excludes the beginning.

Backward induction proves or computes a finite sequence of statements by starting at its terminal index and stepping toward the initial index.

A counterexample is one instance satisfying a claim’s hypotheses but not its conclusion, and therefore disproves the universal claim.

Structural induction proves a property of every recursively generated object by checking the initial objects and showing that every construction rule preserves the property.

For an admissible predicate on lazy lists $P$, prove $P(\perp )$ and $P([])$, and prove $P(xs)\Rightarrow P(x:xs)$ for every possibly partial head $x$. Constructor induction then establishes $P$ on every finite partial approximation, and admissibility extends it to limits, including infinite lists. Without the bottom value case and the limit condition, ordinary finite structural induction does not justify a claim about infinite data.^[ref]

A predicate on possibly partial lists is admissible when it holds at the limit of every increasing chain of finite approximations on which it holds. Increasing here means replacing a bottom value by more defined information while retaining already defined constructors and values. This closure condition permits a property established for finite approximations to pass to an infinite list. The predicate “the list is finite” lacks this closure: every finite prefix ending in an undefined tail is finite in extent, but their limit may have infinitely many constructors.

A probability-preserving bijection pairs outcomes of two events without changing their masses, proving the events have equal probability.