Mathematical Induction
Mathematical induction is a proof technique used to establish that a statement P(n) holds for all natural numbers n by verifying a base case and then proving an inductive step. In the inductive step, one assumes P(k) is true (the inductive hypothesis) and derives that P(k+1) must also be true. This technique is analogous to a line of dominoes: knocking the first triggers an infinite chain.
Key Formula
If P(1) is true and P(k) implies P(k+1), then P(n) is true for all natural numbers n
LaTeX: P(1) \text{ true, and } P(k) \Rightarrow P(k+1) \Rightarrow P(n) \text{ true } \forall n \in \mathbb{N}
| Symbol | Meaning | Unit |
|---|---|---|
| P(n) | Proposition or statement depending on natural number n | none |
| k | Arbitrary natural number used as inductive hypothesis | none |
| n | Any natural number for which the statement is claimed | none |
Worked Example
Problem
Prove that the sum of the first n natural numbers equals n(n+1)/2.
Solution
Step 1 (Base case): For n = 1, LHS = 1, RHS = 1(2)/2 = 1. True. Step 2 (Inductive hypothesis): Assume 1 + 2 + ... + k = k(k+1)/2 for some k ≥ 1. Step 3 (Inductive step): Show it holds for k+1. LHS for k+1: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) [by inductive hypothesis] = (k+1)[k/2 + 1] = (k+1)(k+2)/2 = (k+1)((k+1)+1)/2 [matches RHS for n = k+1] Step 4: By induction, the formula holds for all n ∈ ℕ.
Answer
1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n. (Proven by induction.)
Structure of a Mathematical Induction Proof
| Step | Name | What to Do | Example (Sum formula) |
|---|---|---|---|
| 1 | Base Case | Verify P(1) directly | Sum(1) = 1 = 1(2)/2 ✓ |
| 2 | Inductive Hypothesis | Assume P(k) is true | Assume sum up to k = k(k+1)/2 |
| 3 | Inductive Step | Prove P(k) ⟹ P(k+1) | Add (k+1) to both sides |
| 4 | Conclusion | State result for all n | Formula holds for all n ∈ ℕ |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Proof by Contradiction
Proof by contradiction (reductio ad absurdum) is a logical proof technique in which one assumes the negation of the statement to be proved, then derives a logical contradiction, thereby establishing the original statement's truth. It relies on the law of the excluded middle: a proposition is either true or false, with no middle ground. Classic examples include proofs that √2 is irrational and that there are infinitely many prime numbers.
Pigeonhole Principle
The Pigeonhole Principle states that if n items are placed into m containers and n > m, then at least one container must hold more than one item. It is a fundamental combinatorial tool used to prove the existence of certain configurations without constructing them explicitly. Applications range from proving that two people in a city share a birthday to guaranteeing collisions in hash functions.
Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
The word "induction" comes from Latin inductio, meaning "leading into." The method was used informally by ancient Greek mathematicians but was first clearly articulated by Francesco Maurolico in 1575. Blaise Pascal applied it systematically in 1665, and Augustus De Morgan formalised and named the technique in the 19th century.