Mathematical Induction — Mathematics Knowledge System

Overview

Mathematical induction is a proof technique for establishing that a statement P(n) holds for every natural number n. It works like an infinite row of dominoes: show the first domino falls (base case), and show that any falling domino knocks over the next one (inductive step). Together those two facts guarantee every domino falls.

Intuition

Suppose you want to prove something is true for every natural number — infinitely many statements at once. You can't check them all by hand. Induction sidesteps this: prove the very first case directly, then prove a single general rule — 'if it works for some number, it works for the next one.' That single rule, applied over and over starting from the base case, covers every natural number, the same way one falling domino guarantees all the rest fall.

Formal Definition

Definition

The principle of mathematical induction (weak form):

\Big(P(0) \land \forall k \in \mathbb{N}\,(P(k) \Rightarrow P(k+1))\Big) \Rightarrow \forall n \in \mathbb{N}\, P(n)

If P holds at 0, and P(k) implies P(k+1) for every k, then P holds for all natural numbers.

Notation

Notation	Meaning
$P(n)$	The statement to be proven, parameterized by n
$P(k) \Rightarrow P(k+1)$	The inductive step: assuming P(k) (the inductive hypothesis), prove P(k+1)

Proofs

Sum of the first n positive integers

$P(n): 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ (Statement to prove)
$P(1): 1 = \frac{1(2)}{2} = 1$ (Base case holds)
$\text{Assume } P(k): 1+\cdots+k = \frac{k(k+1)}{2}$ (Inductive hypothesis)
$1+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ (Add (k+1) to both sides and factor — this is exactly P(k+1))
$\therefore P(n) \text{ holds for all } n \geq 1$ (By the principle of induction)

Properties

Strong induction

P(k) may assume P(0), P(1), \dots, P(k) all hold, not just P(k) alone.

Example: Used to prove every integer > 1 has a prime factorization.

Applications

Correctness proofs for recursive algorithms and loop invariants rely directly on induction.

Worked Examples

Base case n=0: 2^0 = 1 > 0. True.
$2^0 = 1 > 0$
Assume 2^k > k. Show 2^{k+1} > k+1.
$2^{k+1} = 2 \cdot 2^k > 2k$
Since k ≥ 0, 2k ≥ k+1 whenever k ≥ 1 (and check k=0 separately), so 2^{k+1} > k+1.
$2k \geq k+1$

Answer: True for all n ≥ 0 by induction.

Practice Problems

Difficulty 3/10

Prove by induction that the sum of the first n odd numbers equals n².

Difficulty 5/10

In computer science, why is mathematical induction the natural tool to prove a recursive function is correct?

Difficulty 4/10

Use induction to state the proof outline that 1 + 2 + ... + n = n(n+1)/2 (the formula behind an O(n²) nested-loop count).

Common Mistakes

Common Mistake

Forgetting to prove the base case, and jumping straight to the inductive step.

Without a verified base case, the inductive step proves nothing — 'P(k) implies P(k+1)' says nothing about whether P(0) is even true.

Common Mistake

Assuming what you're trying to prove instead of assuming only P(k).

The inductive hypothesis is P(k) alone — you may not assume P(n) for the n you're ultimately trying to reach.

Quiz

In a proof by induction, what must be shown in the base case?

P(n) for all nP(0) or P(1), the starting valueP(k+1) directlyNothing — only the inductive step matters

Flashcards

1 / 2

Historical Background

Implicit uses of induction appear in Euclid's proof of the infinitude of primes (c. 300 BCE), but the first fully explicit statement of the principle is credited to Francesco Maurolico in 1575, who used it to prove that the sum of the first n odd numbers is n². Blaise Pascal used it systematically in 1665, and the name 'mathematical induction' was popularized by Augustus De Morgan in the 1830s.

1575
Maurolico gives the first explicit inductive proof
Francesco Maurolico
1665
Pascal applies induction systematically in his Traité du triangle arithmétique
Blaise Pascal
1838
De Morgan coins the term 'mathematical induction'
Augustus De Morgan

Summary

Induction proves P(n) for all natural numbers using two steps: base case and inductive step.
Base case: verify P holds for the smallest n (usually 0 or 1).
Inductive step: assume P(k), prove P(k+1) follows.
Strong induction assumes all of P(0)...P(k), useful for prime factorization proofs.
Analogy: an infinite row of dominoes — first one falls, each one knocks over the next.

References

WebsiteWikipedia — Mathematical induction