Mathematical Induction

Picture a row of dominoes standing on edge, stretching off into the distance. You flick the first one. It falls onto the second. The second falls onto the third. The third onto the fourth. You never touch any domino after the first, yet every single one falls.

Two things made this happen. First, someone knocked over domino number one. Second, the dominoes were arranged so that each one, when it falls, takes the next one down with it. Neither fact alone is enough — if you never pushed the first domino, nothing starts; if the dominoes are too far apart, the chain breaks at some gap. But the two facts together guarantee that every domino falls, no matter how far the line extends.

Mathematical induction is exactly this idea, applied to the positive integers. You have a statement P(n) — some claim that depends on a positive integer n — and you want to prove it for every n. You prove it for n = 1 (push the first domino), and then you prove that whenever it holds for n = k, it also holds for n = k + 1 (each domino knocks the next). The two steps together prove P(n) for all n \geq 1.

This technique is the backbone of proofs about positive integers. The formula for the sum 1 + 2 + 3 + \dots + n, the formula for the sum of a geometric series, divisibility properties, inequalities that hold for large n — all of these yield to induction. The technique is not hard to learn, but it requires one shift in thinking: instead of trying to prove the statement for all n at once, you prove it for a single generic step and let the chain reaction do the rest.

The two pieces of an induction proof

An induction proof has exactly two parts, and both are required.

Base case. Verify that the statement P(n) is true for the smallest value of n you care about — usually n = 1, though sometimes n = 0 or n = 2 depending on the problem. This is a direct check: plug in the number and confirm the statement holds.

Inductive step. Assume that P(k) is true for some arbitrary positive integer k (this assumption is called the inductive hypothesis), and use that assumption to prove P(k+1).

The inductive step is where all the work happens. You are not assuming the conclusion — you are assuming a specific instance of the statement (P(k)) and deriving the next instance (P(k+1)). The assumption is legitimate because the base case established that at least one instance is true, and the inductive step shows the truth propagates forward: from P(1) to P(2), from P(2) to P(3), from P(3) to P(4), and so on, without end.

The principle is an axiom of the natural numbers — it is built into the very definition of what the positive integers are. You cannot prove it from simpler facts about arithmetic; it is one of the foundational rules. (The going-deeper section below explains its connection to the well-ordering principle.)

A first taste: the sum 1 + 2 + 3 + \dots + n

There is a famous formula: the sum of the first n positive integers is \frac{n(n+1)}{2}. You can verify it for small cases — when n = 4, the sum is 1 + 2 + 3 + 4 = 10, and \frac{4 \cdot 5}{2} = 10. But checking finitely many cases does not prove the formula for all n. Induction does.

Claim. For every positive integer n,

Base case (n = 1). The left side is 1. The right side is \frac{1 \cdot 2}{2} = 1. They match.

Inductive step. Assume the formula holds for n = k:

Now consider the sum up to k + 1:

The right side is \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.

This is exactly the formula with n replaced by k + 1: \frac{(k+1)((k+1)+1)}{2}. So P(k+1) holds.

By induction, the formula holds for every positive integer n. \square

The key move was adding (k+1) to both sides of the assumed equation, then simplifying. The inductive hypothesis gave you the sum up to k; you extended it by one term and showed the formula still works. That single step, combined with the base case, covers every positive integer — an infinite number of cases settled by one finite argument.

The structure of the inductive step

The inductive step is the heart of every induction proof, and it always follows the same rhythm:

1. Write down the inductive hypothesis. Assume P(k) is true. Write it out explicitly — the formula, the inequality, the divisibility statement, whatever P(k) says.

2. Write down the goal. What does P(k+1) look like? Write it out explicitly too. Now you can see exactly where you need to arrive.

3. Bridge the gap. Start from something involving k + 1 (the left side of P(k+1), say) and manipulate it until you can use the inductive hypothesis to replace part of the expression. Then simplify until you reach the right side of P(k+1).

The bridge is the creative part — the part that requires you to see how P(k) connects to P(k+1). In summation formulas, the bridge is usually "peel off the last term and apply the hypothesis to the rest." In divisibility problems, the bridge is often "rewrite f(k+1) - f(k)" in a useful way. In inequalities, the bridge might involve bounding one side.

Two worked examples

Strong induction

Sometimes the inductive step needs more than just P(k) — it needs P(1), P(2), \dots, P(k), all at once. This is strong induction (also called complete induction).

Strong induction looks more powerful than ordinary induction, but it is logically equivalent — anything provable by one is provable by the other. The difference is in convenience. Some statements — especially those involving division, prime factorisation, or recursion that jumps back more than one step — are much easier to prove with the full set of previous cases available.

A classic use: proving that every integer n \geq 2 can be written as a product of primes. The base case is n = 2, which is already prime (a product of one prime). For the inductive step, assume every integer from 2 to k can be factored into primes. Consider k + 1: if it is prime, it is a product of one prime and you are done. If it is composite, then k + 1 = a \cdot b where 2 \leq a, b \leq k. By the strong inductive hypothesis, both a and b factor into primes, so k + 1 = a \cdot b factors into primes too. This is the existence half of the Fundamental Theorem of Arithmetic.

The well-ordering connection

The principle of mathematical induction is equivalent to the well-ordering principle:

Every non-empty set of positive integers has a smallest element.

This statement sounds almost too obvious to be interesting, but it is exactly what makes induction work. Here is why. Suppose P(n) satisfies the base case and the inductive step, but fails for some positive integer. Let S be the set of all positive integers for which P(n) is false. By well-ordering, S has a smallest element — call it s. Since P(1) is true (base case), s > 1, so s - 1 is a positive integer. And s - 1 < s, so s - 1 is not in S, meaning P(s-1) is true. But the inductive step says P(s-1) \implies P(s), so P(s) is true — contradicting the fact that s \in S. The contradiction means S must be empty: P(n) holds for all n.

This proof connects three powerful ideas — induction, well-ordering, and proof by contradiction — into a single tight argument.

The interactive figure below lets you explore why induction needs both pieces. Drag the point to choose a starting domino (the base case). The readout shows which dominoes fall if the inductive step holds from that starting point onward.

Common confusions

• "The inductive hypothesis is circular — you're assuming what you want to prove." No. You are assuming P(k) for one specific k and proving P(k+1) — a different statement. The base case anchors the chain, and the inductive step extends it one link at a time. There is no circular reasoning: the logic is sequential, not circular.

• "You can skip the base case." You cannot. Without the base case, the inductive step proves nothing — it says "if any domino falls, the next one falls too," but no domino ever starts the chain. A false statement can satisfy the inductive step while failing the base case. For instance, "n = n + 1" satisfies the inductive step vacuously (if k = k + 1 then k + 1 = k + 2 — both sides increase by 1), but it fails for every n because the base case fails.

• "Induction only works starting at n = 1." Induction works starting at any integer. If you verify the base case at n = 5 and prove the inductive step for k \geq 5, you get the result for all n \geq 5. The starting point depends on the problem.

• "Strong induction is stronger than ordinary induction." The two forms are logically equivalent — they prove exactly the same set of statements. Strong induction is just more convenient in certain situations because it gives you a bigger hypothesis to work with. Anything provable by strong induction is also provable by ordinary induction (with a more clever reformulation of P(n)), and vice versa.

• "Induction proves why a formula is true." Induction proves that a formula is true, but it does not always explain why. The sum-of-squares formula is proved correct by induction, but the proof does not reveal where the formula \frac{n(n+1)(2n+1)}{6} comes from. To understand why, you might need a different approach — a geometric argument, a telescoping trick, or a combinatorial interpretation. Induction is a verification engine, and a powerful one, but it is not the only source of mathematical understanding.

Going deeper

Peano's axioms and why induction is an axiom

The positive integers are formally defined by a set of axioms due to the Italian mathematician Giuseppe Peano. One of those axioms is the principle of mathematical induction. The other axioms define 1 as a natural number, define a "successor" function S(n) = n + 1, and state that no two different numbers have the same successor. Together, these axioms pin down the natural numbers uniquely — and induction is the axiom that prevents "extra" elements from sneaking in. Without induction, you could have a system that satisfies all the other axioms but contains elements that are not reachable from 1 by repeated succession. Induction says: if a property holds for 1 and is preserved by the successor, then everything in the system has the property. It is the axiom that guarantees there are no stowaways.

Transfinite induction

Ordinary induction works on the natural numbers because they are well-ordered — every non-empty subset has a least element. But the well-ordering principle can be extended to other ordered sets, leading to transfinite induction. This is the technique used to prove results about uncountably infinite sets, ordinal numbers, and the deeper reaches of set theory. The structure is the same — base case, inductive step — but the "next element" is not always n + 1; it might be a limit of all previous elements. Transfinite induction is a topic for university mathematics, but its roots are in the same idea you learned here: prove the first case, prove the passage from each case to the next, and conclude the result for all cases.

Induction in competition mathematics

Indian competitions (RMO, INMO, and the selection tests for the International Mathematical Olympiad) use induction constantly. A typical competition trick is strengthening the inductive hypothesis: if the statement P(n) is hard to prove by induction because P(k) \implies P(k+1) does not go through, you replace P(n) with a stronger statement Q(n) (which implies P(n)) for which the inductive step does go through. The paradox — making the thing you need to prove harder — is one of the great insights of competition mathematics, and it comes up repeatedly in inequality problems and combinatorics.

Where this leads next

Induction is a tool that shows up throughout mathematics whenever statements about the positive integers need to be proved.

• Number Theory Basics — divisibility, primes, and the Fundamental Theorem of Arithmetic all rely on induction (especially strong induction) for their proofs.
• Sequences and Series — summation formulas, recursive definitions, and convergence results are natural territory for induction.
• Proof by Contradiction — the connection between induction and well-ordering passes through contradiction, and the technique of infinite descent is induction running backwards.
• Mathematical Proof — Direct Proof — the inductive step is itself a direct proof (assuming P(k), deriving P(k+1)), so the skills from direct proof are the building blocks of every induction argument.
• Binomial Theorem — the expansion of (a + b)^n can be proved by induction, and the connection between binomial coefficients and Pascal's triangle is a beautiful induction-friendly story.