What Is Mathematical Induction?
Mathematical induction is a method of proof that shows a statement is true for every natural number, by checking a single starting case and then showing each case forces the next. It is the standard tool for any claim that begins "for all $n$", where testing every value one by one is impossible because there are infinitely many.
Write the claim as $P(n)$, a statement that depends on a whole number $n$. Proving $P(n)$ for all $n$ by induction means proving exactly two things.
Base case. Show that $P(1)$ is true (or $P(n_0)$ for whatever the smallest relevant value is).
Inductive step. Show that if $P(k)$ is true for some $k$, then $P(k+1)$ is true as well.
The assumption "$P(k)$ is true" that you make inside the inductive step has a name: the inductive hypothesis. It is a temporary "what if", not a fact you have proved, and knowing the difference is most of what separates a correct induction proof from a broken one. The natural numbers this runs over are the counting numbers $1, 2, 3, \dots$; see natural number for the exact set.
How Does Mathematical Induction Work?
The two steps combine into a chain. The base case knocks over the first domino. The inductive step is a guarantee that any domino, once it falls, knocks over the one after it. Put those together and every domino falls: $P(1)$ is true, so $P(2)$ is true, so $P(3)$ is true, and so on without end.
Table: The skeleton every induction proof follows.
Step | What you write | What it establishes |
|---|---|---|
Base case | Check $P(1)$ directly | The chain has a first true case |
Inductive hypothesis | Assume $P(k)$ is true | A temporary "what if" to build on |
Inductive step | Derive $P(k+1)$ from $P(k)$ | Every true case forces the next |
Conclusion | State $P(n)$ holds for all $n$ | The whole chain falls |
How Do You Prove The Sum Of The First N Natural Numbers?
This is the most famous induction proof, and it confirms the closed form for the sum of natural numbers, the same running total you meet again in an arithmetic progression.
Example 1: Prove that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for every natural number $n$.
Call the statement $P(n)$.
Base case ($n = 1$): the left side is $1$, and the right side is $\dfrac{1(1+1)}{2} = 1$. Both sides agree, so $P(1)$ is true.
Inductive step: assume $P(k)$ holds for some $k \geq 1$, that is
$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}$$
Add the next term, $(k+1)$, to both sides:
$$1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$
Now factor the right side over a common denominator:
$$\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 original formula with $k+1$ written in place of $n$. So $P(k)$ forces $P(k+1)$.
Final answer: the base case holds and the inductive step holds, so $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ for every natural number $n$.
How Do You Prove The Sum Of The First N Odd Numbers?
The odd numbers give the cleanest inductive step in all of algebra, because the term you add is always the next odd number. The result, that the running total is a perfect square, matches the closed form for the sum of odd numbers.
Example 2: Prove that $1 + 3 + 5 + \dots + (2n-1) = n^2$ for every natural number $n$.
Base case ($n = 1$): the left side is $1$ and the right side is $1^2 = 1$. So $P(1)$ is true.
Inductive step: assume $P(k)$ holds, that is
$$1 + 3 + 5 + \dots + (2k-1) = k^2$$
The next odd number after $(2k-1)$ is $(2k+1)$. Add it to both sides:
$$1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + (2k+1)$$
The right side is a perfect-square trinomial:
$$k^2 + 2k + 1 = (k+1)^2$$
That is $P(k+1)$. So each case forces the next.
Final answer: $1 + 3 + 5 + \dots + (2n-1) = n^2$ for every natural number $n$.
How Do You Use Induction To Prove Divisibility?
Induction is not only for sums. It proves divisibility claims too, and the trick is to split the $k+1$ expression into "a piece the hypothesis already handles" plus "a piece you can see is divisible".
Example 3: Prove that $3^{2n} - 1$ is divisible by $8$ for every natural number $n$.
Base case ($n = 1$): $3^{2} - 1 = 9 - 1 = 8$, which is divisible by $8$. So $P(1)$ is true.
Inductive step: assume $P(k)$ holds, so $3^{2k} - 1 = 8m$ for some integer $m$. Rearranged, $3^{2k} = 8m + 1$. Now look at the next case:
$$3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 9 \cdot 3^{2k} - 1$$
Substitute $3^{2k} = 8m + 1$:
$$9(8m + 1) - 1 = 72m + 9 - 1 = 72m + 8 = 8(9m + 1)$$
Since $9m + 1$ is an integer, $3^{2(k+1)} - 1$ is a multiple of $8$. That is $P(k+1)$.
Final answer: $3^{2n} - 1$ is divisible by $8$ for every natural number $n$.
What Is Strong Induction?
Strong induction lets you assume the statement for every value up to $k$, that is $P(1), P(2), \dots, P(k)$ all at once, in order to prove $P(k+1)$. Ordinary induction gives you only the single case right before; strong induction hands you the whole history. You reach for it when the next case leans on more than just the one directly before it.
A classic example is prime factorization: every integer $n \geq 2$ is a product of primes. To prove it for $n+1$, either $n+1$ is prime (done), or it splits as $a \times b$ with both $a$ and $b$ smaller than $n+1$, and the strong hypothesis already guarantees each of those factors into primes. Ordinary induction cannot reach $a$ and $b$ directly, because they need not be $n$; strong induction can.
Table: How ordinary induction and strong induction differ.
Feature | Ordinary induction | Strong induction |
|---|---|---|
What you assume | $P(k)$ only | $P(1), P(2), \dots, P(k)$ |
Best when | each case depends on the one before | each case depends on several earlier cases |
Typical example | sum of the first $n$ numbers | prime factorization, Fibonacci facts |
The two are logically equivalent in power. Anything provable one way is provable the other; strong induction is simply more convenient when a case reaches further back.
What Happens If You Skip The Base Case?
The inductive step can be airtight and the statement still false. That is why the base case is not a formality, and the fastest way to feel it is to watch a "proof" go wrong.
Take the claim $P(n): 1 + 3 + 5 + \dots + (2n-1) = n^2 + 3$.
Inductive step: assume the sum equals $k^2 + 3$. Add the next odd number, $(2k+1)$:
$$k^2 + 3 + (2k + 1) = (k^2 + 2k + 1) + 3 = (k+1)^2 + 3$$
The inductive step goes through perfectly: $P(k)$ forces $P(k+1)$ for every $k$. Yet the statement is false. Check the base case: at $n = 1$ the left side is $1$ and the right side is $1^2 + 3 = 4$, and $1 \neq 4$.
The chain of implications is real, but it is anchored to nothing, so it proves nothing. The true sum is $n^2$, exactly as Example 2 showed.
A valid inductive step tells you the dominoes are lined up correctly. Only the base case tells you the first one actually falls.
Why Does Mathematical Induction Work?
Induction is not a trick or an act of faith. It follows from a basic fact about the natural numbers called the well-ordering principle: every non-empty set of natural numbers has a smallest member. Here is how that fact guarantees the method.
Suppose induction failed. Then some natural numbers make $P(n)$ false. Collect all of them into a set. By well-ordering, that set has a smallest element; call it $m$, the first place the statement breaks.
The base case rules out $m = 1$. You proved $P(1)$ is true, so the first counterexample cannot be $1$. That means $m > 1$, and $m - 1$ is a natural number.
The inductive step rules out everything else. Because $m$ is the smallest counterexample, $P(m-1)$ must be true. But the inductive step says $P(m-1)$ forces $P(m)$, so $P(m)$ is true after all, contradicting that $m$ was a counterexample.
No smallest counterexample can survive both steps, so there is no counterexample at all. That is the whole engine behind the domino image: the base case removes the first failure, the inductive step removes any "first failure" further along, and together they leave nowhere for a false case to hide.
Who Invented Mathematical Induction?
The idea is far older than its name. Mathematicians were arguing "from one case to the next" centuries before anyone drew the dominoes or wrote $P(k+1)$, including early work tied to the binomial theorem.
Two later mathematicians pushed the method toward the form we use now.
Francesco Maurolico (1494–1575, Italy) used induction in his 1575 book Arithmeticorum libri duo to prove that the sum of the first $n$ odd numbers equals $n^2$, the very result proved in Example 2.
Blaise Pascal (1623–1662, France) gave the first explicit statement of the principle in his Traité du triangle arithmétique (1665), using it to establish the patterns inside Pascal's triangle.
Where Is Mathematical Induction Used In The Real World?
Induction leaves the classroom and goes straight into computer science, where "prove it works for every input" is a daily requirement.
Algorithm correctness: programmers prove that an algorithm returns the right answer for inputs of every size by checking the smallest input, then showing that correctness on size $k$ carries to size $k+1$.
Recursion that terminates: a recursive function reduces a problem to smaller versions of itself, and induction is what proves the process always reaches its stopping point instead of running forever.
Data structures: properties of trees, linked lists, and heaps are proved by structural induction, a version of the same idea applied to structures built up piece by piece.
Complexity analysis: the time and space formulas for recursive algorithms, such as the cost of a merge sort, are confirmed by induction on the input size.
Combinatorics: counting formulas and identities that feed into algorithms are established the same way.
One method for proving a claim about every whole number turns out to underwrite the software that runs a phone, a search engine, and a bank. A proof technique from algebra class is quietly holding up the machines around you.
What Are The Most Common Mathematical Induction Mistakes?
These three errors account for most lost marks on induction, confirmed against the Stanford CS103 guide to inductive proofs, a CMU discrete-math "errors and pitfalls" handout, and a widely used false-proofs worksheet.
Skipping or misreading the base case.
Where it slips in:
A student jumps straight to the inductive step, or checks a starting value for which the statement does not actually hold.
Don't do this:
Do not treat the base case as a warm-up to rush past. An inductive step with no valid base case proves nothing, exactly as the $n^2 + 3$ example showed.
The correct way:
Verify the smallest case explicitly. Compute both sides, or check the divisibility, for the starting value (usually $n = 1$) before you touch the inductive step.
Assuming what you are trying to prove.
Where it slips in:
Inside the inductive step, a student writes down $P(k+1)$ as if it were already true and rearranges it until both sides match.
Don't do this:
Do not start from $P(k+1)$ and work toward something true. That is circular: it uses the conclusion to justify the conclusion.
The correct way:
Start from the inductive hypothesis $P(k)$, which you are allowed to assume, and build up to $P(k+1)$ by one valid move, such as adding the next term, multiplying, or factoring.
Off-by-one errors moving from $k$ to $k+1$.
Where it slips in:
A student adds the wrong "next term" or substitutes $k+1$ carelessly, so the two sides drift out of the pattern.
Don't do this:
Do not guess the next term. In the odd-numbers sum, the term after $(2k-1)$ is $(2k+1)$, not $(2k-1)+1$.
The correct way:
Write $P(k+1)$ out in full first, replacing every $n$ with $k+1$, so you know the exact target expression before any algebra begins.
Practice Problems On Mathematical Induction
Prove each statement by induction unless the problem says otherwise. Answers and hints follow each line.
Prove $2 + 4 + 6 + \dots + 2n = n(n+1)$.
(Answer: base $n=1$ gives $2 = 1 \cdot 2$; the step adds $2(k+1)$ to $k(k+1)$ to get $(k+1)(k+2)$.)Prove $1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$.
(Answer: base $n=1$ gives $1 = 2^1 - 1$; the step adds $2^k$ to $2^k - 1$ to get $2^{k+1} - 1$.)Prove that $n^2 + n$ is divisible by $2$ for every natural number $n$.
(Answer: base $n=1$ gives $2$; the step writes $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$, and both parts are even.)Prove $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.
(Answer: base $n=1$ gives $1$; add $(k+1)^2$ to the hypothesis and factor to $\dfrac{(k+1)(k+2)(2k+3)}{6}$.)A classmate "proves" $1 + 3 + \dots + (2n-1) = n^2 + 5$ with a fully correct inductive step and stops there. What is missing, and is the claim true?
(Answer: the base case, and the claim is false: at $n=1$ the sum is $1$ but $n^2 + 5 = 6$.)
Where Should You Go Next After Mathematical Induction?
Induction is a tool you will reach for again and again, and a few directions build on it naturally.
Sum of cubes of n natural numbers. A clean formula to prove with the exact two-step method from this article.
Sum of n terms of an AP. Where the closed formulas that induction confirms actually come from.
Pascal's triangle. The array al-Karaji and Pascal studied, packed with patterns that induction can prove.
To build this habit of proof with a live trainer who starts from why each step is needed, explore the Bhanzu algebra classes.
Was this article helpful?
Your feedback helps us write better content