What Is Mathematical Induction?
Mathematical induction is a proof technique for showing that a statement holds for every integer from some starting value onward. Write the statement as $P(n)$, a claim that depends on a whole number $n$. To prove $P(n)$ is true for all integers $n \ge n_0$, you carry out exactly two steps.
$$ \textbf{1. Base case: } P(n_0) \text{ is true.} \qquad \textbf{2. Inductive step: } P(k) \Rightarrow P(k+1). $$
The base case checks the very first value, usually $n_0 = 1$ (sometimes $0$, or wherever the claim is meant to begin).
The inductive step assumes $P(k)$ is true for an arbitrary $k \ge n_0$, this assumption is called the inductive hypothesis, and uses it to prove $P(k+1)$.
Once both steps are done, the logic cascades. The base case gives $P(n_0)$, and the inductive step turns it into $P(n_0+1)$, then $P(n_0+1)$ into $P(n_0+2)$, and so on without end. Every integer from $n_0$ up is reached, so $P(n)$ is true for all of them. That cascade is the whole idea the sections below make concrete.
How Do You Write A Proof By Mathematical Induction?
Every induction proof follows the same four-part skeleton. Learning the skeleton once means you can attack any of them the same way.
Table: The four parts of every proof by mathematical induction.
Part | What you write | What it does |
|---|---|---|
State $P(n)$ | The exact claim, as an equation or property depending on $n$ | Fixes precisely what must be proved |
Base case | Check $P(n_0)$ by direct substitution | Shows the first domino falls |
Inductive hypothesis | "Assume $P(k)$ is true for some $k \ge n_0$" | The one thing you are allowed to use |
Inductive step | Use the hypothesis to derive $P(k+1)$ | Shows each domino topples the next |
The domino picture keeps the two halves honest. The base case is knocking over the first domino, and the inductive step guarantees that any domino, once it falls, pushes over the one after it. Miss the first and nothing starts; miss the second and the chain breaks somewhere. You need both.
One rule governs the inductive step, and it is where marks are won or lost: you must actually use the inductive hypothesis. If your proof of $P(k+1)$ never refers back to $P(k)$, you have not done induction at all, you have just tried to prove $P(k+1)$ from scratch.
How Do You Prove The Sum Of The First n Natural Numbers?
The classic first proof is the formula for adding up $1 + 2 + 3 + \cdots + n$. It is the same running total behind an arithmetic progression, and induction pins it down exactly.
Claim $P(n)$:
$$\sum_{i=1}^{n} i = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$
Base case ($n = 1$). The left side is just $1$. The right side is $\dfrac{1(1+1)}{2} = \dfrac{2}{2} = 1$. Both sides equal $1$, so $P(1)$ holds.
Inductive hypothesis. Assume for some $k \ge 1$ that
$$\sum_{i=1}^{k} i = \frac{k(k+1)}{2}.$$
Inductive step. Add the next term, $(k+1)$, to both sides and simplify toward the target $\dfrac{(k+1)(k+2)}{2}$:
$$ \sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1) $$
$$ = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}. $$
That last expression is exactly the formula with $n = k+1$, so $P(k) \Rightarrow P(k+1)$. By induction, the formula holds for every integer $n \ge 1$.
Numeric check ($n = 3$): the sum is $1 + 2 + 3 = 6$, and $\dfrac{3(3+1)}{2} = \dfrac{12}{2} = 6$. The two agree.
How Do You Prove The Sum Of The First n Squares?
The next-hardest standard proof is the sum of squares, $1^2 + 2^2 + \cdots + n^2$. The pattern of work is identical; only the algebra grows.
Claim $P(n)$:
$$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$
Base case ($n = 1$). The left side is $1^2 = 1$. The right side is $\dfrac{1(2)(3)}{6} = \dfrac{6}{6} = 1$. So $P(1)$ holds.
Inductive hypothesis. Assume for some $k \ge 1$ that $\displaystyle\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$.
Inductive step. Add $(k+1)^2$ and factor $(k+1)$ out of the result:
$$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} $$
$$ = \frac{(k+1)\big[,k(2k+1) + 6(k+1),\big]}{6} = \frac{(k+1)\big(2k^2 + 7k + 6\big)}{6}. $$
The quadratic factors as $2k^2 + 7k + 6 = (k+2)(2k+3)$, giving
$$ \sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}. $$
That is the formula with $n = k+1$, since $2(k+1)+1 = 2k+3$. The step is proved, so by induction $P(n)$ holds for all $n \ge 1$.
Numeric check ($n = 3$): the sum is $1 + 4 + 9 = 14$, and $\dfrac{3(4)(7)}{6} = \dfrac{84}{6} = 14$. They match.
How Do You Use Mathematical Induction For Divisibility?
Induction is not only for sum formulas. It proves divisibility and inequality claims too. Here is a clean divisibility proof.
Claim $P(n)$: $n^3 - n$ is divisible by $6$ for every integer $n \ge 1$.
Base case ($n = 1$). $1^3 - 1 = 0$, and $0$ is divisible by $6$. So $P(1)$ holds.
Inductive hypothesis. Assume $k^3 - k = 6m$ for some integer $m$.
Inductive step. Expand $(k+1)^3 - (k+1)$ and split off the hypothesis:
$$ (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k $$
$$ = (k^3 - k) + 3k(k+1). $$
The first piece, $k^3 - k$, is divisible by $6$ by the hypothesis. In the second piece, $k(k+1)$ is a product of two consecutive integers, so one of them is even, which makes $3k(k+1)$ a multiple of $6$. A multiple of $6$ plus a multiple of $6$ is a multiple of $6$, so $(k+1)^3 - (k+1)$ is divisible by $6$. By induction, $P(n)$ holds for all $n \ge 1$.
Numeric check ($n = 2$): $2^3 - 2 = 6 = 6 \times 1$. And ($n = 3$): $3^3 - 3 = 24 = 6 \times 4$. Both are multiples of $6$.
What Is Strong Induction?
Sometimes proving $P(k+1)$ needs more than just $P(k)$; it needs several earlier cases at once. Strong induction allows exactly that. The base case is the same, but the inductive hypothesis becomes "assume $P(j)$ is true for every $j$ from $n_0$ up to $k$," and from that fuller assumption you prove $P(k+1)$.
A short example makes the difference clear.
Claim: every integer $n \ge 2$ can be written as a product of prime numbers.
Base case ($n = 2$). $2$ is prime, so it is a product of primes (itself).
Strong hypothesis. Assume every integer from $2$ up to $k$ is a product of primes.
Step. Consider $k+1$. If $k+1$ is prime, it is its own prime product and we are done. If it is not prime, then $k+1 = a \times b$ with $2 \le a, b \le k$. By the strong hypothesis, $a$ and $b$ are each products of primes, so their product $k+1$ is too.
Ordinary induction could not run this argument, because $k+1 = a \times b$ says nothing about $P(k)$ specifically; it points back to two smaller cases that could be anywhere below $k+1$. Strong induction is standard induction with a wider hypothesis, and the two are logically equivalent.
Why Does Mathematical Induction Work?
It can feel like a trick: you "assume what you are proving," yet the conclusion is airtight. It is not a trick, and here is the reasoning underneath it.
The cascade is finite for any target. Pick any integer $n$. The base case establishes $P(n_0)$, and the inductive step, applied $n - n_0$ times, walks you from $P(n_0)$ up to $P(n)$ in finitely many moves. No single value is ever "assumed for free."
The well-ordering principle guarantees no gaps. Every non-empty set of positive integers has a smallest member. Suppose $P(n)$ failed somewhere; then the set of "bad" values would have a smallest element, call it $b$. It cannot be $n_0$ (the base case rules that out), so $b - 1$ is a valid earlier value where $P$ is true, and the inductive step then forces $P(b)$ to be true, contradicting $b$ being bad. No smallest counterexample can exist, so there is no counterexample at all.
You are not assuming the whole claim. The inductive hypothesis assumes only the single case $P(k)$, not the universal statement. You then earn $P(k+1)$ from it. That is deduction, not circular reasoning.
Both views describe the same fact. The domino image is the intuition; the well-ordering principle is the formal guarantee. This is why an induction proof, done correctly, settles infinitely many cases with a finite amount of writing.
Who Invented Mathematical Induction?
The method is far older than its name. Reasoning "if it holds for one, it holds for the next" appears in mathematics centuries before anyone called it induction.
The name is slightly misleading, which is worth knowing. In everyday science, "induction" means guessing a general rule from examples, which is never certain. Mathematical induction is the opposite: it is fully rigorous deduction, and its conclusions are proved, not guessed.
Where Is Mathematical Induction Used In The Real World?
Induction is the backbone of rigor whenever a claim covers infinitely many cases or a process repeats without a fixed end.
Computer science and algorithms: proving a program is correct for inputs of every size uses induction on the input length, and proving a recursive function terminates and returns the right answer is induction on the depth of the recursion.
Loop invariants: to show a loop does its job, engineers prove a property holds before the loop and is preserved by each pass, which is induction on the number of iterations.
Series and sequence formulas: closed forms for sums, like the ones above and those behind a geometric progression, are certified by induction rather than by checking a few terms.
Discrete math and combinatorics: counting arguments, graph and tree properties, and identities such as those from the binomial theorem are routinely established by induction.
Foundations of calculus: many results that lead into limits and calculus, including properties of sequences and their partial sums, rest on an inductive step somewhere in their proof.
The common thread is trust at scale. Testing a claim for $n = 1, 2, 3$ is evidence, not proof; induction is what upgrades "it seems to always work" into "it provably always works."
What Are The Most Common Mistakes With Mathematical Induction?
These four errors account for most lost marks on induction, and they are the exact failures flagged in Cornell and CMU proof guides and in student-help threads.
Skipping or misplacing the base case.
Where it slips in:
A student writes a flawless inductive step and stops, or checks $n = 0$ when the claim is only meant to start at $n = 1$.
Don't do this:
Do not treat the base case as a formality. Without a true first domino, the step proves nothing, and the whole chain can be false.
The correct way:
Verify $P(n_0)$ by direct substitution at the exact starting value the claim requires, and state that value explicitly.
Assuming what you are trying to prove.
Where it slips in:
In the hypothesis a student writes "assume $P(n)$ is true for all $n$," which quietly assumes the whole result and leaves nothing to prove.
Don't do this:
Do not assume the universal statement. That is circular, and a grader will not award it.
The correct way:
Assume only the single case $P(k)$ for one arbitrary $k \ge n_0$, then deduce $P(k+1)$ from it.
Never actually using the inductive hypothesis.
Where it slips in:
A student proves $P(k+1)$ directly, from scratch, without ever substituting the assumed $P(k)$. The write-up looks fine but is not an induction proof.
Don't do this:
Do not ignore the hypothesis. If $P(k)$ appears nowhere in your derivation of $P(k+1)$, the link between dominoes is missing.
The correct way:
Make the substitution visible. In the sum proofs above, the step begins by replacing $\sum_{i=1}^{k} i$ with $\frac{k(k+1)}{2}$, which is the hypothesis doing its job.
Proving the step in the wrong direction.
Where it slips in:
A student starts from $P(k+1)$, manipulates it down to $P(k)$, and calls it done. That shows $P(k+1) \Rightarrow P(k)$, the reverse of what is needed.
Don't do this:
Do not begin the algebra from the thing you want to conclude. Starting with the target and reaching something true proves nothing on its own.
The correct way:
Begin from what is known ($P(k)$ or the $(k+1)$-term expression built on it) and work forward until you reach $P(k+1)$.
Practice Problems On Mathematical Induction
Prove each by induction (answers and key steps follow). Assume $n$ is a positive integer unless stated otherwise.
Prove $2 + 4 + 6 + \cdots + 2n = n(n+1)$.
(Answer: base $n=1$ gives $2 = 1\cdot 2$; step: $n(n+1) + 2(n+1) = (n+1)(n+2)$.)Prove $1 + 3 + 5 + \cdots + (2n-1) = n^2$.
(Answer: base $n=1$ gives $1 = 1^2$; step: $k^2 + (2k+1) = (k+1)^2$.)Prove $\sum_{i=1}^{n} i^3 = \left(\dfrac{n(n+1)}{2}\right)^2$.
(Answer: base $n=1$ gives $1 = 1$; step: add $(k+1)^3$ and factor to $\left(\dfrac{(k+1)(k+2)}{2}\right)^2$.)Prove $3^n - 1$ is divisible by $2$ for all $n \ge 1$.
(Answer: base $3^1 - 1 = 2$; step: $3^{k+1} - 1 = 3(3^k - 1) + 2$, both terms even.)Prove $2^n > n$ for all $n \ge 1$.
(Answer: base $2^1 = 2 > 1$; step: $2^{k+1} = 2\cdot 2^k > 2k \ge k+1$ for $k \ge 1$.)Prove $n^2 \ge 2n + 1$ for all $n \ge 3$.
(Answer: base $n=3$ gives $9 \ge 7$; step: $(k+1)^2 = k^2 + 2k + 1 \ge (2k+1) + 2k + 1 > 2(k+1)+1$.)
Where Should You Go Next After Mathematical Induction?
Induction is the tool that certifies almost every formula you meet in sequences and series, so the natural next doors build directly on it.
Sequences. The formulas induction proves are statements about sequences and their sums; start here to see the objects the method certifies.
Arithmetic progressions. The sum $1 + 2 + \cdots + n$ is the simplest arithmetic series, and its general sum formula is a direct induction exercise.
Binomial theorem. One of the standard proofs of the binomial expansion is by induction on the exponent, a satisfying next step up in difficulty.
Calculus. Induction underpins many results about sequences and partial sums that lead into limits and series.
If your child is building proof skills, a live Bhanzu trainer teaches mathematical induction starting from the "why" (the domino cascade and the well-ordering guarantee) in the Bhanzu math tutoring program.
Was this article helpful?
Your feedback helps us write better content