The best examples of 3 examples of the principle of mathematical induction (plus more)

Starting with concrete examples of 3 examples of the principle of mathematical induction

Let’s begin exactly where students usually meet induction: three classic, foundational proofs that every math major has seen at least once. These are the “standard set” that most textbooks use as the first examples of 3 examples of the principle of mathematical induction.

Example 1: Sum of the first n positive integers

Claim: For every integer \(n \ge 1\),
[
1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.
]

Base case (n = 1).
Left side: \(1\). Right side: \(\frac{1(1+1)}{2} = 1\). They match.

Inductive step. Assume the formula holds for \(n = k\):
[
1 + 2 + \dots + k = \frac{k(k+1)}{2}.
]
This is the induction hypothesis.

Now prove it for \(n = k+1\):
[
1 + 2 + \dots + k + (k+1).
]
Use the hypothesis on the first \(k\) terms:
[
= \frac{k(k+1)}{2} + (k+1)
= \frac{k(k+1) + 2(k+1)}{2}
= \frac{(k+1)(k+2)}{2}.
]
That’s exactly the formula with \(n = k+1\). So by the principle of mathematical induction, the identity holds for all \(n \ge 1\).

This is often the very first example of induction students see, and it sets the pattern: base case, induction hypothesis, then algebra that transforms \(k\) into \(k+1\).

Example 2: Sum of a geometric series with ratio 2

Claim: For every integer \(n \ge 0\),
[
1 + 2 + 4 + 8 + \dots + 2^n = 2^{n+1} - 1.
]

Base case (n = 0).
Left side: \(2^0 = 1\). Right side: \(2^{0+1} - 1 = 2 - 1 = 1\). Works.

Inductive step. Assume it holds for \(n = k\):
[
1 + 2 + 4 + \dots + 2^k = 2^{k+1} - 1.
]
Now add the next term, \(2^{k+1}\):
[
1 + 2 + \dots + 2^k + 2^{k+1} = (2^{k+1} - 1) + 2^{k+1} = 2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1.
]
That matches the formula with \(n = k+1\). Another clean example of the principle of mathematical induction in action.

Example 3: Inequality involving powers of 2

Claim: For every integer \(n \ge 1\),
[
2^n \ge n + 1.
]

Base case (n = 1).
\(2^1 = 2\) and \(1 + 1 = 2\). So \(2^1 \ge 2\) holds.

Inductive step. Assume \(2^k \ge k + 1\) for some \(k \ge 1\). Then
[
2^{k+1} = 2 \cdot 2^k \ge 2(k + 1) = 2k + 2.
]
We want to show \(2^{k+1} \ge (k+1) + 1 = k+2\). Since \(2k + 2 \ge k + 2\) for all \(k \ge 0\), we’re done:
[
2^{k+1} \ge 2k + 2 \ge k + 2.
]

These three classic cases form the backbone of many courses. When people talk about examples of 3 examples of the principle of mathematical induction, they usually mean something very close to this trio: a sum, a geometric series, and an inequality.

Going beyond the first 3: more real examples of induction that matter

Those first examples are great for learning the pattern, but induction shows up in far richer contexts. Modern combinatorics and computer science courses (see, for example, course notes from places like MIT OpenCourseWare and Harvard’s CS courses) use induction constantly to prove bounds, count structures, and justify algorithms.

Let’s look at several more real examples that push past the initial trio.

Example 4: Sum of the first n odd integers

Claim: For every integer \(n \ge 1\), the sum of the first \(n\) odd numbers is \(n^2\):
[
1 + 3 + 5 + \dots + (2n - 1) = n^2.
]

Base case (n = 1).
Left side: \(1\). Right side: \(1^2 = 1\).

Inductive step. Assume
[
1 + 3 + 5 + \dots + (2k - 1) = k^2.
]
Add the next odd number, \(2(k+1) - 1 = 2k + 1\):
[
1 + 3 + \dots + (2k - 1) + (2k + 1) = k^2 + (2k + 1) = (k + 1)^2.
]
So the statement holds for \(k+1\), and induction finishes the job.

This is a nice bridge between algebra and geometry: if you draw squares made of dots, you literally see each new odd layer wrapping around the previous square.

Example 5: A classic combinatorial identity

Induction shines in combinatorics. Consider the binomial coefficients \(\binom{n}{k}\), which count the number of ways to choose \(k\) objects from \(n\) without order. One famous identity is:
[
\sum_{k=0}^{n} \binom{n}{k} = 2^n.
]

This says “if you add up all the ways to choose any number of elements from an \(n\)-element set, you get \(2^n\),” the number of all subsets.

Base case (n = 0).
Left side: \(\binom{0}{0} = 1\). Right side: \(2^0 = 1\).

Inductive step. Assume
[
\sum_{k=0}^{n} \binom{n}{k} = 2^n. ] Use Pascal’s identity, [ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}, ] which is standard in combinatorics texts and lecture notes (for instance, see discrete math materials from Carnegie Mellon University). Then [ \sum_{k=0}^{n+1} \binom{n+1}{k}
= \sum_{k=0}^{n+1} \bigl(\binom{n}{k} + \binom{n}{k-1}\bigr) = \sum_{k=0}^{n+1} \binom{n}{k} + \sum_{k=0}^{n+1} \binom{n}{k-1}. ] Shift indices carefully (terms outside the range are zero): [ = \sum_{k=0}^{n} \binom{n}{k} + \sum_{k=0}^{n} \binom{n}{k}
= 2 \cdot 2^n = 2^{n+1}.
]
So the identity holds for \(n+1\), and by the principle of mathematical induction we get it for all \(n\).

This is one of the best examples connecting induction to counting arguments you actually see in modern combinatorics and probability.

Example 6: A useful inequality for analysis and algorithms

Here’s a bound that shows up in analysis and in the run-time estimates of algorithms:

Claim: For every integer \(n \ge 1\),
[
1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{n}} \le 2.
]

Base case (n = 1).
\(1 + \tfrac12 = 1.5 \le 2\). Fine.

Inductive step. Assume
[
1 + \frac{1}{2} + \dots + \frac{1}{2^{k}} \le 2.
]
Then for \(k+1\):
[
1 + \frac{1}{2} + \dots + \frac{1}{2^{k}} + \frac{1}{2^{k+1}}
\le 2 + \frac{1}{2^{k+1}} \le 2 + \frac{1}{2} < 3.
]
That’s a bit loose, so refine the hypothesis. A sharper statement, which we can prove by induction, is
[
1 + \frac{1}{2} + \dots + \frac{1}{2^{n}} = 2 - \frac{1}{2^{n}}.
]
Then the base case and inductive step follow the same pattern as Example 2, and the inequality \(\le 2\) is immediate.

Why does this matter? Because series like this appear in error bounds, probability models, and the analysis of divide-and-conquer algorithms in CS courses that are very current in 2024–2025.

Example 7: Induction in recurrence relations (computer science flavor)

Modern algorithm textbooks (like those used in U.S. universities) constantly use induction to prove bounds on recurrences. Take a simple one:
[
T(n) = T(n-1) + 2n - 1, \quad T(1) = 1.
]

Claim: \(T(n) = n^2\) for all integers \(n \ge 1\).

Base case (n = 1).
\(T(1) = 1^2 = 1\).

Inductive step. Assume \(T(k) = k^2\). Then
[
T(k+1) = T(k) + 2(k+1) - 1 = k^2 + 2k + 1 = (k+1)^2.
]
So by induction, \(T(n) = n^2\) for all \(n\).

This is more than a cute identity: it models the total work done by an algorithm that, on input size \(n\), does \(2n-1\) operations plus whatever work was needed for size \(n-1\). Induction is the workhorse that turns the recurrence into a closed form.

Example 8: Strong induction on prime factorization

So far, the examples of 3 examples of the principle of mathematical induction (and the extras) have used ordinary induction: you assume the statement for \(n = k\) and prove it for \(k+1\). Strong induction is a closely related form where you assume the statement holds for all integers up to \(k\), and use that to prove it for \(k+1\).

A famous strong induction result is the Fundamental Theorem of Arithmetic:

Every integer \(n \ge 2\) can be written as a product of prime numbers.

Base case (n = 2).
\(2\) is prime, so it is already a product of primes (just itself).

Inductive step. Assume every integer \(m\) with \(2 \le m \le k\) can be written as a product of primes. Consider \(k+1\):

• If \(k+1\) is prime, we’re done.
• If \(k+1\) is composite, then \(k+1 = ab\) for integers \(a, b\) with \(2 \le a, b \le k\).

By the induction hypothesis, both \(a\) and \(b\) can be written as products of primes. Multiply those factorizations to get a prime factorization of \(k+1\).

This is one of the best examples of how strong induction underpins number theory. The logic here shows up in modern cryptography, coding theory, and anywhere prime factorization matters.

Example 9: Induction with a shifted base case

Not every induction starts at \(n = 1\). Sometimes the statement only becomes true after a certain threshold. For instance, in inequality proofs related to exponential vs. polynomial growth, you might see something like:

Claim: For every integer \(n \ge 5\),
[
2^n > n^2.
]

Base case (n = 5).
\(2^5 = 32\), \(5^2 = 25\), so \(32 > 25\).

Inductive step. Assume \(2^k > k^2\) for some \(k \ge 5\). Then
[
2^{k+1} = 2 \cdot 2^k > 2k^2.
]
We want to show \(2^{k+1} > (k+1)^2 = k^2 + 2k + 1\). So it’s enough to prove
[
2k^2 \ge k^2 + 2k + 1,
]
which simplifies to
[
k^2 - 2k - 1 \ge 0.
]
For \(k \ge 5\), \(k^2 - 2k - 1\) is positive (you can check directly or use a quick bound). So the inequality holds for \(k+1\), and by induction it holds for all \(n \ge 5\).

This kind of argument shows up in up-to-date algorithm analysis and discrete math courses, where comparing growth rates is routine.

Why these are some of the best examples of 3 examples of the principle of mathematical induction

If you look back over all of these, certain patterns repeat. The classic examples of 3 examples of the principle of mathematical induction (sums, geometric series, simple inequalities) do a great job of teaching the structure:

• You anchor the statement with a base case.
• You assume it’s true at step \(k\) (or for all steps up to \(k\)).
• You use that assumption to prove it at \(k+1\).

The more advanced examples include:

• Combinatorial identities (binomial sums) that show up in probability, discrete math, and statistics.
• Inequalities and series that appear in analysis and in modeling error or growth.
• Recurrences that describe the cost of algorithms, a staple in current CS curricula.
• Number theory results like prime factorization, which underlie modern cryptography and coding.

If you’re teaching or learning in 2024–2025, these are not just abstract puzzles. They’re exactly the kind of real examples you’ll see in university lecture notes, online open-course platforms, and standardized contest problems.

For deeper reading on induction and its uses in modern math education and CS, you can explore:

• Induction and recursion in discrete math courses (e.g., materials from MIT OpenCourseWare).
• Proof-writing resources from university math departments, such as those linked via Harvard’s math and CS pages.
• General proof strategy discussions in open education resources like OER Commons, which often include induction modules.

FAQ: common questions about examples of induction

Q1. Why do so many textbooks use the same examples of 3 examples of the principle of mathematical induction?
Because those three — sum of the first \(n\) integers, geometric series with ratio 2, and a basic inequality like \(2^n \ge n+1\) — hit the main patterns you need: algebraic manipulation, handling powers, and working with inequalities. They’re simple enough to compute by hand, but rich enough to show the full logic of induction.

Q2. Can you give another example of induction that feels more “real-world”?
One practical example of induction appears in algorithm analysis. If a sorting algorithm’s running time \(T(n)\) satisfies a recurrence like \(T(n) = T(n-1) + cn\) with \(T(1) = c\), you can use induction to prove that \(T(n) = O(n^2)\). That’s the same structure as Example 7, just with a constant \(c\) carried along.

Q3. Are strong induction and ordinary induction different principles?
Logically, they’re equivalent. Any proof you can do with strong induction can be rewritten with ordinary induction, and vice versa. But for many number-theory problems — like the prime factorization example — strong induction is more natural and keeps the argument cleaner.

Q4. How many examples of induction should I practice to feel comfortable?
Instead of chasing a specific number of examples, aim for variety. Work through the classic examples of 3 examples of the principle of mathematical induction, then add a few inequalities, at least one combinatorial identity, a recurrence from algorithms, and a number-theory statement. That mix will prepare you for most problems you’ll see in courses or contests.

Q5. Where can I find more worked-out examples?
Look at open course materials from universities. Discrete math and introductory proof courses at places like MIT, Harvard, and other research universities often post detailed lecture notes and problem sets online. These include many more real examples of induction, often with full solutions or solution sketches.