Mathematical induction (basic and strong induction) - Discrete Math

SECTION 1

Historical Context & Motivation

How can one prove a statement that must hold for every natural number — an infinite collection — using only a finite argument? This is the fundamental challenge that mathematical induction addresses. Unlike deductive arguments that treat individual cases, induction provides a mechanism for bridging from the finite to the infinite, allowing mathematicians to assert universal truths about the natural numbers with complete rigor. The idea, which rests on the well-ordering principle — the fact that every nonempty subset of the natural numbers has a least element — took centuries to crystallize into the formal proof technique taught in every discrete mathematics course today.

~300 BCE • Euclid's Implicit Induction

In Elements, Euclid's proof that there are infinitely many primes employs reasoning that implicitly mirrors an inductive descent, though he never formalized the method.

~1000 CE • Al-Karaji and Ibn al-Haytham

The Persian mathematician al-Karaji used an early form of induction to prove the binomial theorem and formulas for sums of cubes. Around the same period, Ibn al-Haytham applied similar reasoning in his work on optics and sums of powers.

1665 • Pascal's Explicit Formulation

Blaise Pascal, in Traité du triangle arithmétique, gave one of the first clear and explicit descriptions of proof by induction, applying it systematically to properties of what we now call Pascal's triangle.

1889 • Peano Axioms

Giuseppe Peano formalized the natural numbers using axioms, one of which — the axiom of induction — placed mathematical induction on a fully rigorous, axiomatic foundation within mathematical logic.

20th Century • Strong Induction and Structural Induction

Logicians generalized the inductive principle to strong (complete) induction and structural induction, enabling proofs over recursively defined data structures — a cornerstone of modern computer science.

The central question that induction answers is deceptively simple: if a property holds for one natural number, and if whenever it holds for a number it must also hold for the next, does it hold for all natural numbers? The answer is affirmative, and the resulting proof technique has become one of the most powerful and frequently used tools in all of mathematics and theoretical computer science.

SECTION 2

Core Principles & Definitions

Mathematical induction is a proof technique designed to establish that a predicate P(n) holds for every natural number n ≥ n₀ (where n₀ is typically 0 or 1). Rather than verifying infinitely many individual cases, we reduce the task to two finite obligations. The method comes in two primary flavors — basic (weak) induction and strong (complete) induction — both of which are logically equivalent but differ in the hypothesis available during the inductive step.

Base Case

Verify that the statement P(n₀) is true for the initial value n₀. This anchors the chain of implications and ensures the induction has a starting point.

Inductive Hypothesis (Weak)

In basic induction, assume P(k) holds for some arbitrary but fixed k ≥ n₀. This single assumption is the lever used to prove the next case.

Inductive Hypothesis (Strong)

In strong induction, assume P(j) holds for all j with n₀ ≤ j ≤ k. This broader assumption provides more raw material for the inductive step.

Inductive Step

Using the inductive hypothesis, prove P(k + 1). This creates the logical domino effect: if any one case is true, the next must follow.

Well-Ordering Connection

Induction is equivalent to the well-ordering principle of ℕ: every nonempty subset has a least element. A failed induction would imply a counterexample set with no least element — a contradiction.

✦

KEY TAKEAWAY

Think of induction as an infinite row of dominoes. The base case knocks over the first domino. The inductive step proves that each domino, when it falls, knocks over the next. With both pieces in place, every domino in the infinite line must fall. In basic induction, domino k knocks over domino k + 1 directly. In strong induction, domino k + 1 might need information from all earlier dominoes — imagine it's balanced by a chain attached to every domino before it.

SECTION 3

Visual Explanation

The Domino Chain of Basic Induction

The cyan rectangle on the left represents the base case P(n₀), verified directly. Each violet domino represents a successive case P(1), P(2), P(3), … The amber arrows encode the inductive step: the implication P(k) → P(k + 1). The dashed green rectangle at the right indicates that P(k + 1) must hold for any k, extending the chain indefinitely.

The diagram above captures the essential architecture of a basic induction proof. Notice that the arrow from domino k to domino k + 1 represents a conditional implication: we do not prove P(k) outright during the inductive step; we merely show that if P(k) is true, then P(k + 1) must be true as well. The base case supplies the initial truth value, and the chain of implications propagates it through every natural number. This structure is precisely why induction is classified as an inference rule rather than an axiom in most formal systems — it derives new truths from established ones via modus ponens applied infinitely.

SECTION 4

Mathematical Framework

We now formalize both variants of induction. Let P(n) be a predicate defined on the integers n ≥ n₀, where n₀ is typically 0 or 1. The following two proof schemes are logically equivalent — any statement provable by one form can be proved by the other — but they differ in the strength of the hypothesis available during the inductive step.

Basic (Weak) Induction

PRINCIPLE OF MATHEMATICAL INDUCTION

[P(n₀) ∧ (∀k ≥ n₀ : P(k) → P(k + 1))] → ∀n ≥ n₀ : P(n)

P(n₀) is the base case. The universally quantified implication ∀k ≥ n₀ : P(k) → P(k + 1) is the inductive step. Together they yield the conclusion that P holds for every n ≥ n₀.

Strong (Complete) Induction

PRINCIPLE OF STRONG INDUCTION

[P(n₀) ∧ (∀k ≥ n₀ : (∀j, n₀ ≤ j ≤ k, P(j)) → P(k + 1))] → ∀n ≥ n₀ : P(n)

The key difference: the inductive hypothesis now assumes P(j) for all values j from n₀ up to k, not just for the single value k. This broader assumption is essential when proving P(k + 1) requires information from cases other than the immediate predecessor.

Equivalence with Well-Ordering

WELL-ORDERING PRINCIPLE

∀S ⊆ ℕ : S ≠ ∅ → (∃m ∈ S : ∀s ∈ S, m ≤ s)

Every nonempty subset S of the natural numbers contains a least element m. This principle is logically equivalent to both forms of induction. To see the connection: suppose P(n) fails for some n. Then the set of counterexamples is nonempty, so by well-ordering it has a least element — but the inductive step shows this least counterexample cannot exist.

💡

When to Use Strong Induction

Use strong induction whenever the truth of P(k + 1) depends on cases beyond P(k) alone. Classic examples include the Fundamental Theorem of Arithmetic (every integer ≥ 2 has a prime factorization), where factoring n may require knowing that smaller factors — not just n − 1 — have prime decompositions. Similarly, problems involving recursive sequences like the Fibonacci numbers often require P(k) and P(k − 1) simultaneously, making strong induction the natural choice.

SECTION 5

Basic vs. Strong Induction — A Detailed Comparison

Although basic and strong induction are logically equivalent — anything provable by one is provable by the other — they offer different ergonomics depending on the structure of the problem at hand. The following diagram and comparison table highlight when each variant is most naturally applied and the structural differences in their proof templates.

Left panel: in basic induction, only the single predecessor case P(k) feeds into the proof of P(k + 1), shown by the single violet arrow. Right panel: in strong induction, all cases from P(n₀) through P(k) contribute, shown by the multiple pink dashed arrows. Both target the green node P(k + 1). The bottom section lists canonical applications of each variant.

Feature	Basic Induction	Strong Induction
Inductive Hypothesis	Assume P(k) for one fixed k ≥ n₀	Assume P(j) for all n₀ ≤ j ≤ k
Number of Base Cases	Typically one (n₀)	May require multiple (n₀, n₀ + 1, …)
Logical Strength	Equivalent to strong induction	Equivalent to basic induction
Best For	P(k + 1) depends only on P(k)	P(k + 1) depends on multiple predecessors
Proof Template Length	Often shorter and more direct	Hypothesis is broader; may simplify tricky steps

Structural comparison of the two induction variants

SECTION 6

Worked Examples

Example 1: Basic Induction — Sum of First n Positive Integers

We prove by basic induction that for all n ≥ 1, the sum 1 + 2 + 3 + ··· + n = n(n + 1)/2.

Proof: Σ_{i=1}^{n} i = n(n + 1) / 2

1
Step 1 — State the Predicate

Define P(n) as the statement: 1 + 2 + ··· + n = n(n + 1)/2. We will show P(n) holds for all n ≥ 1.
2
Step 2 — Base Case (n = 1)

The left-hand side is simply 1. The right-hand side is 1(1 + 1)/2 = 2/2 = 1. Since LHS = RHS, P(1) is true.

P(1) verified: 1 = 1 ✓
3
Step 3 — Inductive Hypothesis

Assume P(k) is true for some arbitrary but fixed k ≥ 1. That is, assume 1 + 2 + ··· + k = k(k + 1)/2.
4
Step 4 — Inductive Step (prove P(k + 1))

We must show that 1 + 2 + ··· + k + (k + 1) = (k + 1)(k + 2)/2. Starting from the left-hand side and applying the inductive hypothesis: 1 + 2 + ··· + k + (k + 1) = [k(k + 1)/2] + (k + 1) = k(k + 1)/2 + 2(k + 1)/2 = (k + 1)(k + 2)/2.

P(k + 1) proved: Σ_{i=1}^{k+1} i = (k + 1)(k + 2)/2 ✓
5
Step 5 — Conclusion

By the principle of mathematical induction, P(n) holds for all n ≥ 1. That is, 1 + 2 + ··· + n = n(n + 1)/2 for every positive integer n.

Q.E.D.

Example 2: Strong Induction — Every Integer ≥ 2 Has a Prime Factor

Proof by Strong Induction: Prime Factorization Existence

1
Step 1 — State the Predicate

Define P(n) as: "n can be written as a product of primes." We prove P(n) for all n ≥ 2 by strong induction.
2
Step 2 — Base Case (n = 2)

The integer 2 is itself prime, so it is trivially a product of primes (a product with one factor). Thus P(2) holds.

P(2) verified: 2 is prime ✓
3
Step 3 — Strong Inductive Hypothesis

Assume P(j) is true for every integer j with 2 ≤ j ≤ k, for some arbitrary k ≥ 2. That is, every integer from 2 through k can be expressed as a product of primes.
4
Step 4 — Inductive Step (prove P(k + 1))

Consider k + 1. There are two cases. Case 1: k + 1 is prime. Then it is a product of primes (itself), so P(k + 1) holds. Case 2: k + 1 is composite. Then k + 1 = a × b where 2 ≤ a, b ≤ k. By the strong inductive hypothesis, both a and b can be written as products of primes. Therefore k + 1 = a × b is also a product of primes.

P(k + 1) proved in both cases ✓
5
Step 5 — Conclusion

By the principle of strong induction, every integer n ≥ 2 can be expressed as a product of prime numbers.

Q.E.D.

⚠

Why Strong Induction Was Necessary

In Example 2, the composite case k + 1 = a × b required knowing that both a and b (which could be much smaller than k) have prime factorizations. Basic induction would only give us P(k), not P(a) or P(b). The ability to invoke P(j) for all j ≤ k is precisely what makes strong induction indispensable here.

SECTION 7

Common Pitfalls and Strategic Tips

Induction proofs are elegant but notoriously prone to subtle errors. Students frequently write proofs that "look right" but contain a logical gap — sometimes a missing base case, sometimes a circular argument in the inductive step. Understanding these pitfalls is as important as mastering the technique itself.

Pitfall	Description	How to Avoid
Missing Base Case	The inductive step may be valid but the base case is omitted or incorrect, so the chain never starts. Example: "All horses are the same color" — the inductive step fails at n = 1 → n = 2.	Always verify the base case explicitly. For strong induction, check whether multiple base cases are needed.
Wrong Base Case	The base case is checked at n₀ but the claim actually begins at a different value, or the inductive step requires a different starting point.	Match n₀ to the domain of the claim. Ensure the inductive step's algebra is valid for k = n₀.
Circular Reasoning	Assuming what you want to prove — e.g., starting the inductive step by writing P(k + 1) and manipulating it into P(k).	Always start from the left-hand side of P(k + 1) and derive the right-hand side using P(k), not the reverse.
Insufficient Strong Hypothesis	Using basic induction when the recurrence or structure requires information from multiple predecessors.	If P(k + 1) depends on P(k − 1), P(k − 2), etc., switch to strong induction and verify all necessary base cases.
Off-by-One Errors	Summation bounds, inequality domains, or index shifts are mishandled during the inductive step.	Write out explicitly what P(k) and P(k + 1) say before beginning the algebraic manipulation.

Common induction proof errors and remedies

✦

KEY TAKEAWAY

Think of an induction proof like a software test suite for an infinite-loop program. The base case is the initialization test: does the program start correctly? The inductive step is the loop-invariant check: does each iteration preserve the desired property? If either test fails, the program (proof) is buggy. Both must pass for the correctness guarantee to hold across all iterations (natural numbers).

SECTION 8

Connection to Advanced Theory

Mathematical induction over the natural numbers is the simplest instance of a much broader family of proof techniques that appear throughout mathematics and computer science. Understanding how basic and strong induction generalize prepares you for deeper study in logic, algebra, and algorithm analysis.

Induction Variant	Domain	Key Idea
Basic / Strong Induction	Natural numbers ℕ	Exploits the successor structure of ℕ; base case + inductive step
Structural Induction	Recursively defined data structures (trees, lists, formulas)	Proves a property for all elements of a recursively defined set by verifying base constructors and showing closure under recursive constructors
Transfinite Induction	Ordinal numbers (well-ordered sets beyond ℕ)	Extends induction to infinite ordinals; requires handling limit ordinals as well as successor ordinals
Well-Founded Induction	Any well-founded relation (no infinite descending chains)	The most general form; proves P(x) by assuming P(y) for all y ≺ x under a well-founded order
Noetherian Induction	Noetherian rings and modules (algebra)	Uses the ascending chain condition; every ascending chain of ideals stabilizes, enabling proofs by "no infinite ascent"

Generalizations of mathematical induction

In computer science, the connection between induction and recursion is particularly profound. Every recursive algorithm implicitly relies on an inductive argument for its correctness: the base case of the recursion corresponds to the base case of the induction, and the recursive calls correspond to the inductive hypothesis. Proving that a recursive algorithm terminates and produces correct output is, at its core, a proof by strong induction on the size of the input (or, more generally, on a well-founded measure that decreases with each recursive call). This deep correspondence means that mastering induction is not merely an exercise in discrete mathematics — it is essential training for rigorous reasoning about algorithms, data structures, and programming language semantics.

ℹ

Looking Ahead

In your next courses, you will likely encounter structural induction when reasoning about parse trees, abstract syntax, and type systems. You may also meet loop invariants in algorithm design courses — these are essentially inductive hypotheses applied at each iteration of a loop, with the loop index playing the role of n.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why an induction proof that omits the base case is invalid, even if the inductive step is correctly carried out. Illustrate your answer by describing a false statement for which the inductive step P(k) → P(k + 1) holds for all k ≥ 1, but the statement itself is false.

Show answer

Without a base case, the chain of implications has no starting truth value. A classic example is the false statement P(n): "n = n + 1" for all n ≥ 1. The inductive step is vacuously valid in the following sense: consider a faulty inductive step that merely transforms one absurd equation into another. More concretely, consider P(n): "all natural numbers greater than or equal to n are equal." The inductive step can be set up to appear valid, but P(1) ("all natural numbers ≥ 1 are equal") is clearly false. The inductive step never fires because there is no true base case to trigger the chain. This demonstrates that both components — base case and inductive step — are logically necessary, not merely conventional.

Question 2: BASIC CALCULATION

Prove by basic induction that for all n ≥ 1: 1² + 2² + 3² + ··· + n² = n(n + 1)(2n + 1) / 6.

Show answer

Base case (n = 1): LHS = 1² = 1. RHS = 1 × 2 × 3 / 6 = 1. ✓ Inductive step: Assume the formula holds for some k ≥ 1. Then 1² + ··· + k² + (k + 1)² = k(k + 1)(2k + 1)/6 + (k + 1)². Factor out (k + 1): (k + 1)[k(2k + 1)/6 + (k + 1)] = (k + 1)[k(2k + 1) + 6(k + 1)] / 6 = (k + 1)(2k² + 7k + 6) / 6 = (k + 1)(k + 2)(2k + 3) / 6 = (k + 1)((k + 1) + 1)(2(k + 1) + 1) / 6. This is exactly the formula with n = k + 1. By induction, the identity holds for all n ≥ 1.

Question 3: INTERMEDIATE

Prove by induction that for all n ≥ 4, 2ⁿ > n². Carefully identify the base case and note where the constraint n ≥ 4 is essential.

Show answer

Base case (n = 4): 2⁴ = 16 > 16 = 4²? No — 16 = 16, so we need a strict inequality. In fact, 2⁵ = 32 > 25 = 5² works, but let's check: 2⁴ = 16, 4² = 16, so equality, not strict. We adjust: the claim should be verified starting at n = 5 if we want strict inequality, or we note that many textbooks state 2ⁿ ≥ n² for n ≥ 4, with strict inequality for n ≥ 5. Taking n₀ = 5: 2⁵ = 32 > 25 = 5². ✓ Inductive step: Assume 2ᵏ > k² for some k ≥ 5. Then 2ᵏ⁺¹ = 2 × 2ᵏ > 2k². We need 2k² ≥ (k + 1)² = k² + 2k + 1, which requires k² ≥ 2k + 1, i.e., k² − 2k − 1 ≥ 0. For k ≥ 3, k² − 2k − 1 = (k − 1)² − 2 ≥ 0 when k ≥ 3. Since k ≥ 5 > 3, the condition holds, and 2ᵏ⁺¹ > (k + 1)². The constraint n ≥ 4 (or 5) is essential because 2³ = 8 < 9 = 3², so the inequality fails for n = 3.

Question 4: APPLIED

Use strong induction to prove that every positive integer n ≥ 2 can be written as a sum of (not necessarily distinct) powers of 2 — that is, every n has a binary representation. (Hint: consider whether n is even or odd.)

Show answer

Base case (n = 2): 2 = 2¹, which is a power of 2. ✓ (One may also verify n = 1: 1 = 2⁰.) Strong inductive hypothesis: Assume every integer j with 1 ≤ j ≤ k can be written as a sum of powers of 2. Inductive step: Consider k + 1. Case 1: k + 1 is even, so k + 1 = 2m where 1 ≤ m ≤ k. By the strong hypothesis, m =

2^{a₁}

+ ··· + 2^{aᵣ}, so k + 1 =

2^{a₁+1}

+ ··· + 2^{aᵣ+1}. Case 2: k + 1 is odd, so k + 1 = 2m + 1 where m ≥ 1 and m ≤ k. By the strong hypothesis, m has a binary representation, so k + 1 = 2m + 2⁰, which is a sum of powers of 2. In both cases, P(k + 1) holds, completing the strong induction. This is a natural application of strong induction because the even case requires P(m) where m = (k + 1)/2, which could be much less than k.

Question 5: CRITICAL THINKING

The following is a famous fallacious induction proof: "All horses are the same color." Let P(n) be "in any set of n horses, all horses are the same color." The base case P(1) is trivially true (a single horse is the same color as itself). For the inductive step, assume P(k). Given a set of k + 1 horses {h₁, h₂, …, h_{k+1}}, consider the subsets {h₁, …, hₖ} and {h₂, …, h_{k+1}}, each of size k. By P(k), all horses in each subset share one color. Since the subsets overlap (they share h₂, …, hₖ), all k + 1 horses must be the same color. Identify the precise logical error in this proof.

Show answer

The error lies in the transition from P(1) to P(2), not in the general inductive step. When k = 1 and we consider the set {h₁, h₂} of 2 horses, the two subsets of size 1 are {h₁} and {h₂}. These subsets do not overlap — the "shared" elements h₂, …, hₖ form an empty set when k = 1. Therefore, we cannot conclude that h₁ and h₂ are the same color. The inductive step is valid for k ≥ 2 (where the overlap is nonempty), but it fails at the critical first application k = 1 → k + 1 = 2. This classic fallacy beautifully illustrates why the base case and the first application of the inductive step deserve careful scrutiny. The proof implicitly assumes k ≥ 2 in the inductive step (to guarantee nonempty overlap), so one would actually need P(2) as a base case — and P(2) is false.

SUMMARY

Lesson Summary

Summary

Mathematical induction is a proof technique for establishing that a predicate P(n) holds for every natural number n ≥ n₀. It consists of two parts: a base case (verifying P(n₀) directly) and an inductive step (showing that if P(k) is true, then P(k + 1) must follow). In basic (weak) induction, the inductive hypothesis assumes only P(k); in strong (complete) induction, it assumes P(j) for all j from n₀ to k. Both forms are logically equivalent and derive their validity from the well-ordering principle of the natural numbers.

Key pitfalls include omitting the base case, circular reasoning in the inductive step, and using basic induction when the recurrence demands the broader hypothesis of strong induction. The technique generalizes to structural induction (over recursively defined structures), transfinite induction (over ordinals), and well-founded induction (over any well-founded relation). In computer science, induction underpins the correctness proofs for recursive algorithms and loop invariants, making it one of the most practically important techniques in all of mathematics.