Mathematical Induction

A complete guide to weak induction, its logical structure, variants, and common proof gaps.

Claim → evidence → conclusion. A claim or task is translated into assumptions or inputs and a target or output, supported by a finite chain of valid steps, and closed by reconnecting the result to the original goal.

Precise definition

The principle of mathematical induction states: if $P(n_0)$ is true and, for every integer $k\ge n_0$, $P(k)\Rightarrow P(k+1)$, then $P(n)$ is true for all integers $n\ge n_0$. The base case anchors the chain; the inductive step proves every link.

Notation and mathematical language

In the inductive step, $P(k)$ is the inductive hypothesis, assumed for an arbitrary $k\ge n_0$ only to prove $P(k+1)$. Strong induction may assume $P(n_0),\ldots,P(k)$ to prove the next case. It is equivalent in power to ordinary induction but often fits recurrences and factorization arguments better.

Conceptual picture

Imagine an infinite row of dominoes beginning at $n_0$. The base case knocks down the first; the inductive implication ensures that whenever an arbitrary domino falls, the next falls. Checking many early dominoes without proving the link does not reach the infinite tail.

Fully worked example

Interpretation and application

Induction verifies loop invariants, recursive algorithms, divisibility patterns, inequalities, and formulas for finite structures. It establishes exact claims, not empirical trends. A computer check of the first million cases can support debugging but cannot replace the inductive link.