Mathematical Induction — Weak and Strong Forms

⚡ Key Takeaways

Mathematical Induction is a proof technique for statements about all natural numbers $n \geq n_0$ . One-line statement: if a property holds for a base case and "passes" from each number to the next, it holds for all numbers from the base on. Key result: proving $P(n_0)$ plus $P(k) \Rightarrow P(k+1)$ establishes $P(n)$ for every $n \geq n_0$ . Applies to: sums, divisibility, inequalities, recurrences, geometry, algorithm correctness. Who/when: formalized by Pascal (1654) and Maurolico (1575); name coined by De Morgan (1838).

💡 The Core Insight

Think of an infinite line of dominoes. You do not need to push each one. You need exactly two facts: 1. The first domino falls (base case). 2. Whenever a domino falls, it knocks over the next (inductive step). From these two facts alone, logic guarantees all dominoes fall. Induction converts an infinite verification into one base check plus one universal "if-then" — a finite amount of work yielding an infinite conclusion.

DefinitionThe Natural Numbers and the Predicate

Let $P(n)$ be a statement (predicate) defined for each integer $n \geq n_0$ , where $n_0$ is a fixed starting integer (usually $0$ or $1$ ). We want to prove:

1

\quad \forall n \geq n_0,\ P(n)\ \text{is true.}

Derivation hint: this is the universally-quantified target; everything below exists to establish it. Symbols: $n$ is the variable natural number; $n_0$ the base index; $P(n)$ a truth-valued statement about $n$ ; $\forall$ means "for all."

TheoremPrinciple of Weak (Ordinary) Mathematical Induction

Suppose:

2

\quad P(n_0)\ \text{is true} \quad \text{(base case)}

Derivation hint: directly verify the statement at the single starting value.

3

\quad \forall k \geq n_0,\ \big(P(k) \Rightarrow P(k+1)\big) \quad \text{(inductive step)}

Derivation hint: assume $P(k)$ (the inductive hypothesis) and deduce $P(k+1)$ by algebra/logic. Then $P(n)$ holds for all $n \geq n_0$ . The conjunction of [2] and [3] implies [1].

TheoremPrinciple of Strong (Complete) Mathematical Induction

Suppose:

4

\quad P(n_0)\ \text{is true (and possibly several base cases)}

Derivation hint: verify enough small cases to anchor the recurrence's depth.

5

\quad \forall k \geq n_0,\ \Big(\big(P(n_0)\wedge P(n_0{+}1)\wedge\cdots\wedge P(k)\big) \Rightarrow P(k+1)\Big)

Derivation hint: assume the statement for ALL integers from $n_0$ up to $k$ , then prove it for $k+1$ . Then $P(n)$ holds for all $n \geq n_0$ . The difference from weak induction is the richer hypothesis: you may use any earlier case, not just the immediately preceding one.

💡 The Core Insight

Strong and weak induction are logically equivalent — anything provable by one is provable by the other. Strong induction is not "stronger" in what it can prove; it is merely a more convenient packaging when $P(k+1)$ naturally depends on cases earlier than $P(k)$ (e.g. $a_{n} = a_{n-1} + a_{n-2}$ ). You can always simulate strong induction by applying weak induction to the auxiliary statement $Q(n):\ \text{"}P(m)\text{ holds for all } n_0 \le m \le n\text{."}$

ProofInduction Follows from Well-Ordering

We prove weak induction using the Well-Ordering Principle (WOP): every nonempty set of natural numbers contains a least element.

Step 1 — Set up a contradiction. Suppose [2] and [3] hold but [1] fails. Define the "failure set"

6

\quad S = \{\, n \geq n_0 : P(n)\ \text{is false}\,\}.

Derivation hint: collect exactly the counterexamples; assuming [1] fails means $S \neq \varnothing$ .

Step 2 — Extract a least counterexample. Since $S$ is a nonempty set of integers bounded below by $n_0$ , WOP gives a least element $m \in S$ . So $P(m)$ is false.

Step 3 — Locate it past the base. By [2], $P(n_0)$ is true, so $m \neq n_0$ ; hence $m > n_0$ and $m - 1 \geq n_0$ .

Step 4 — Predecessor is true. Because $m$ is the least counterexample, $m-1 \notin S$ , so $P(m-1)$ is true.

Step 5 — Apply the inductive step. Setting $k = m-1$ in [3]: $P(m-1) \Rightarrow P(m)$ . Since $P(m-1)$ is true, $P(m)$ is true.

Step 6 — Contradiction. Step 2 says $P(m)$ is false; Step 5 says it is true. Contradiction. Hence $S = \varnothing$ and [1] holds. $\blacksquare$ The strong form follows identically: at Step 4, all of $P(n_0),\dots,P(m-1)$ are true (none are in $S$ ), so [5] yields $P(m)$ .

∎

Figure

The domino chain: base case fires, the implication propagates indefinitely

mathematician · Augustus De Morgan | 1806–1871

The British mathematician Augustus De Morgan coined the very term "mathematical induction" in his 1838 article Induction (Mathematics) for the Penny Cyclopædia. He carefully distinguished it from the inductive reasoning of natural science (generalizing from observations, which is not certain) and emphasized that the mathematical version is deductively valid. De Morgan also made foundational contributions to symbolic logic — including De Morgan's Laws — and helped establish a rigorous, axiomatic spirit that the later Peano axioms would formalize. His naming gave a unified identity to a method mathematicians had used implicitly for centuries.

🧠 Intuition

Why does checking two things prove infinitely many? Because the inductive step is itself an infinite supply of implications packaged in one statement. Saying " $P(k) \Rightarrow P(k+1)$ for all $k$ " secretly asserts:

P(n_0)\Rightarrow P(n_0{+}1),\quad P(n_0{+}1)\Rightarrow P(n_0{+}2),\quad \dots

The base case lights the first link; each implication is a ready-built bridge to the next. Walking the chain from $n_0$ to any target $n$ takes finitely many steps, even though no single proof "reaches the end." Induction is not magic about infinity — it is the recognition that every natural number is reachable from $n_0$ by finitely many $+1$ steps, which is precisely the structure the natural numbers are built to have.

ExampleWeak Induction — Sum of the First n Odd Numbers

Claim: $P(n):\ 1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \geq 1$ .

Base case ( $n=1$ ): LHS $= 1$ ; RHS $= 1^2 = 1$ . ✓

Inductive hypothesis: assume $1+3+\cdots+(2k-1) = k^2$ for some $k \geq 1$ .

Inductive step: add the next odd number $2(k+1)-1 = 2k+1$ :

7

\quad \underbrace{1+3+\cdots+(2k-1)}_{=\,k^2} + (2k+1) = k^2 + 2k + 1 = (k+1)^2.

Derivation hint: substitute the hypothesis $k^2$ , then factor the perfect square $k^2+2k+1$ . This is exactly $P(k+1)$ . By weak induction, the claim holds for all $n \geq 1$ .

\boxed{\,1 + 3 + \cdots + (2n-1) = n^2\quad\text{for all integers } n \geq 1\,}

Check with $n=4$ : $1+3+5+7 = 16 = 4^2$ . ✓

ExampleStrong Induction — Fibonacci Recurrence Lower Bound

Claim: Define $F_1 = 1,\ F_2 = 1,\ F_n = F_{n-1} + F_{n-2}$ . Then $F_n \geq \left(\tfrac{3}{2}\right)^{n-2}$ for all $n \geq 1$ . (We use strong induction because $F_{n}$ depends on two prior terms.)

Base cases:

$n=1$ : $F_1 = 1 \geq (3/2)^{-1} = 0.667$ . ✓
$n=2$ : $F_2 = 1 \geq (3/2)^{0} = 1$ . ✓

Strong inductive hypothesis: assume $F_m \geq (3/2)^{m-2}$ for all $1 \le m \le k$ , with $k \geq 2$ .

Inductive step (prove for $k+1$ ):

8

\quad F_{k+1} = F_k + F_{k-1} \geq \left(\tfrac{3}{2}\right)^{k-2} + \left(\tfrac{3}{2}\right)^{k-3} = \left(\tfrac{3}{2}\right)^{k-3}\!\left(\tfrac{3}{2}+1\right) = \left(\tfrac{3}{2}\right)^{k-3}\cdot\tfrac{5}{2}.

Derivation hint: apply the hypothesis to BOTH $F_k$ and $F_{k-1}$ , then factor out the smaller power. Since $\tfrac{5}{2} = 2.5 \geq \tfrac{9}{4} = (3/2)^2 = 2.25$ :

9

\quad F_{k+1} \geq \left(\tfrac{3}{2}\right)^{k-3}\cdot\left(\tfrac{3}{2}\right)^{2} = \left(\tfrac{3}{2}\right)^{k-1} = \left(\tfrac{3}{2}\right)^{(k+1)-2}.

Derivation hint: replace $5/2$ by the smaller $9/4=(3/2)^2$ to keep the inequality, then combine exponents. This is $P(k+1)$ . By strong induction the bound holds for all $n \geq 1$ .

\boxed{\,F_n \geq \left(\tfrac{3}{2}\right)^{n-2}\quad\text{for all } n \geq 1\,}

Check $n=10$ : $F_{10}=55$ , and $(3/2)^8 \approx 25.6$ , so $55 \geq 25.6$ . ✓

⚠️ The base case is not optional decoration

The inductive step alone proves nothing. " $P(k)\Rightarrow P(k+1)$ " can be perfectly true while $P(n)$ is false for every $n$ — if the chain never starts. You need both an anchored base and a valid step. Likewise, strong induction requires enough base cases: if your inductive step uses $P(k-1)$ , then $P(n_0)$ alone may not anchor it — you may need $P(n_0)$ and $P(n_0+1)$ both verified explicitly (as in the Fibonacci example).

CounterexampleInductive step holds, conclusion is false — missing base

False claim: " $P(n):\ n = n+1$ for all $n$ ."

Bogus inductive step: Assume $P(k)$ , i.e. $k = k+1$ . Add $1$ to both sides: $k+1 = k+2$ , which is $P(k+1)$ . So the implication $P(k)\Rightarrow P(k+1)$ is genuinely valid! Yet the claim is absurd. Why no contradiction? There is no valid base case: $P(1)$ says $1=2$ , which is false. With no first domino, the entire chain collapses despite a flawless inductive step. Lesson: never skip the base case.

CounterexampleAll horses are the same color — a flawed inductive step

False claim (Pólya): "In any set of $n$ horses, all are the same color."

Base ( $n=1$ ): one horse, trivially same color. ✓ Step: given $n$ horses $h_1,\dots,h_{n+1}$ , the first $n$ are same color (hypothesis) and the last $n$ are same color (hypothesis), so by overlap all $n+1$ match.

The flaw: the "overlap" argument fails when $n+1 = 2$ , because $\{h_1\}$ and $\{h_2\}$ share no horse — there is nothing to transmit the color. The step $P(1)\Rightarrow P(2)$ is broken, so the chain never propagates. Lesson: the inductive step must hold for every $k \geq n_0$ , including the very first transition.

connection

Mathematical induction sits at the foundation of discrete mathematics and connects widely:

<a class="wiki-link" href="/wiki/math-found-well-ordering-principle">Well-Ordering Principle</a> — logically equivalent to induction; provides the contradiction backbone of the proof.
Peano Axioms — induction is literally one of the axioms defining the natural numbers; it is not derived but assumed at the foundational level.
Recursion and Recurrence Relations — recursion constructs objects step-by-step; induction proves properties of those objects. They are mirror images.
Structural Induction — generalizes the idea from numbers to trees, lists, formulas, and other recursively-built structures used in computer science.
<a class="wiki-link" href="/wiki/math-found-proof-by-contradiction">Proof by Contradiction</a> — the engine inside the WOP-based justification of induction.
Transfinite Induction — extends the method past the natural numbers to all ordinals using well-ordered sets.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid: uses implicit inductive-style reasoning (e.g. the infinitude of primes), though without an explicit principle.

- c. 1000 — al-Karaji & later al-Samaw'al: Islamic mathematicians employ a recursive argument resembling induction for the binomial coefficients and sums of cubes.

- 1575 — Francesco Maurolico: in Arithmeticorum libri duo, gives one of the first explicit inductive proofs (sum of odd numbers equals a square), recognized as an early systematic use.

- 1654 — Blaise Pascal: in Traité du triangle arithmétique, states and uses the method with full clarity for properties of Pascal's triangle — often cited as the first rigorous formulation.

- 1686 — Jacob Bernoulli: explicitly defends and uses induction, criticizing incomplete arguments and sharpening the logic.

- 1838 — Augustus De Morgan: coins the term "mathematical induction" and distinguishes it from scientific induction.

- 1889 — Giuseppe Peano: formalizes induction as an axiom of the natural numbers in Arithmetices principia, placing it on rigorous foundations.

- 1888 — Richard Dedekind: in Was sind und was sollen die Zahlen?, independently develops the inductive/recursive characterization of

\mathbb{N}

.

- 20th century: induction generalizes to transfinite induction (Cantor's ordinals) and structural induction in logic and computer science.

open-problem · Where induction's reach ends — and Gödel's shadow

Induction over $\mathbb{N}$ is complete for properties of natural numbers in the sense that any true universal arithmetic statement provable from the Peano axioms is provable using the induction schema. Yet there are profound limits:

Gödel incompleteness (1931): there exist true statements about natural numbers that the Peano axioms (including induction over first-order formulas) cannot prove. Induction does not capture all arithmetic truth.
Goodstein's theorem is a true statement about natural numbers that provably cannot be proven using ordinary (first-order) induction — it requires transfinite induction up to the ordinal $\varepsilon_0$ . This shows the weak/strong forms over $\mathbb{N}$ are genuinely weaker than transfinite induction.
Choosing the right induction variable is sometimes an art: a statement may be hard to induct on directly but easy after strengthening the hypothesis (proving a more general claim that gives a more useful inductive step). Finding the right strengthening is a recurring research-flavored challenge.
Open meta-question for learners: which problems require strong induction versus weak? Formally none (they are equivalent), but the practical boundary — when does the extra hypothesis genuinely simplify a proof — remains a matter of mathematical taste and experience.

Mathematical Induction — Weak and Strong Forms

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also