Mathematical Induction

Mathematical induction is one of the most important proof methods in discrete mathematics, students. It is especially useful when you want to prove that a statement is true for every whole number starting at some point, like $n=1$, $n=0$, or $n=5$. Think of it like a row of dominoes 🎯: if the first domino falls, and each domino knocks over the next one, then all the dominoes fall. Induction turns that idea into a rigorous proof.

What You Will Learn

By the end of this lesson, students, you should be able to:

explain the main ideas and terminology behind mathematical induction,
use induction to prove statements about integers,
connect induction to proof techniques in discrete mathematics,
recognize when induction is a good choice,
describe how induction fits into the larger topic of proof techniques II.

Mathematical induction appears often in computer science, algebra, number theory, and proofs about algorithms. It is especially powerful for statements involving patterns, recursive processes, and formulas that depend on $n$.

The Basic Idea of Induction

A proof by induction has two main parts:

Base case: prove the statement is true for the first value.
Inductive step: assume it is true for one value $n$, then prove it is true for the next value $n+1$.

If both parts are successful, then the statement is true for all values in the range you started with.

A common way to write an induction proof is:

Let $P(n)$ be the statement we want to prove.
Show $P(1)$ is true, or $P(0)$ if the starting point is $0$.
Assume $P(k)$ is true for some arbitrary integer $k \ge 1$.
Use that assumption to prove $P(k+1)$ is true.
Conclude that $P(n)$ is true for all $n \ge 1$.

The assumption that $P(k)$ is true is called the inductive hypothesis. It is not a guess; it is a temporary assumption used only inside the proof of the next case.

Why Induction Works

The logic of induction is similar to climbing stairs 🪜. If you can stand on the first step, and every step lets you move to the next one, then you can reach any step above it.

In formal terms, the base case proves the statement starts correctly. The inductive step proves the truth of one case forces the truth of the next case. Together, they create a chain reaction:

$$P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow P(4) \Rightarrow \cdots$$

Because every later case depends on an earlier one, proving the first link and the linking rule is enough.

This method is connected to the well-ordering principle, which says every nonempty set of positive integers has a least element. If a statement were false for some positive integers, there would be a smallest false one. The inductive step would force it to be true if the previous one is true, creating a contradiction. That is one reason induction is logically sound.

Example 1: A Sum Formula

Let us prove the well-known formula:

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

for all integers $n \ge 1$.

Base Case

For $n=1$:

$$1 = \frac{1(1+1)}{2} = 1$$

So $P(1)$ is true.

Inductive Step

Assume $P(k)$ is true for some $k \ge 1$:

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Now we must prove $P(k+1)$:

$$1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

Starting from the inductive hypothesis:

$$1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

Factor out $(k+1)$:

$$\frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\left(\frac{k+2}{2}\right)$$

So:

$$1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

This is exactly $P(k+1)$.

Conclusion

Since the base case is true and the inductive step is true, the formula holds for all $n \ge 1$.

This example shows a common pattern in induction: assume the formula for $k$, then use algebra to prove it for $k+1$.

Example 2: Divisibility

Now let us prove a statement involving divisibility.

Prove that $7^n - 1$ is divisible by $6$ for all integers $n \ge 1$.

We want to show:

$$6 \mid (7^n - 1)$$

Base Case

For $n=1$:

$$7^1 - 1 = 6$$

and $6$ is divisible by $6$, so the statement is true.

Inductive Step

Assume for some $k \ge 1$ that

$$7^k - 1 = 6m$$

for some integer $m$. This means $7^k - 1$ is divisible by $6$.

Now consider $7^{k+1} - 1$:

$$7^{k+1} - 1 = 7 \cdot 7^k - 1$$

Add and subtract $7$ in a helpful way:

$$7^{k+1} - 1 = 7(7^k - 1) + 6$$

Using the inductive hypothesis, $7^k - 1$ is divisible by $6$, so $7(7^k - 1)$ is also divisible by $6$. Also, $6$ is divisible by $6$. Therefore their sum is divisible by $6$.

So $7^{k+1} - 1$ is divisible by $6$.

Why This Works

Induction often needs algebraic rewriting. You do not just “plug in” the next value; you transform the expression until the inductive hypothesis appears naturally.

Common Terms You Should Know

Here are the main words used in induction proofs, students:

Proposition or statement: the claim being proved, such as $P(n)$.
Base case: the first value checked.
Inductive hypothesis: the assumption that $P(k)$ is true.
Inductive step: the proof that $P(k) \Rightarrow P(k+1)$.
Conclusion: the statement is true for all required integers.

A strong induction proof uses a slightly different hypothesis, but in ordinary induction, you assume only one previous case, $P(k)$.

How to Recognize When Induction Fits

Induction is a good method when the statement has one of these forms:

a formula involving $n$,
a property of all integers $n \ge n_0$,
a recursively defined sequence,
a statement about steps in an algorithm,
a claim that builds one case from the previous case.

Examples include formulas for sums, inequalities, divisibility rules, recurrence relations, and properties of trees or graphs.

For example, to prove an inequality like

$$2^n \ge n+1$$

for all $n \ge 0$, induction is a natural tool because the statement depends on the integer $n$ and the step from $n$ to $n+1$ is manageable.

A Quick Inequality Example

Let us prove:

$$2^n \ge n+1$$

for all integers $n \ge 0$.

Base Case

For $n=0$:

$$2^0 = 1 \ge 0+1 = 1$$

So the base case is true.

Inductive Step

Assume $2^k \ge k+1$ for some $k \ge 0$.

We need to show:

$$2^{k+1} \ge k+2$$

Start with the left side:

$$2^{k+1} = 2 \cdot 2^k$$

Using the inductive hypothesis:

$$2^{k+1} \ge 2(k+1)$$

Now compare $2(k+1)$ and $k+2$:

$$2(k+1) = 2k+2 \ge k+2$$

for all $k \ge 0$. Therefore:

$$2^{k+1} \ge k+2$$

So the statement is true for $k+1$.

This example shows that induction can prove inequalities, not just equalities.

Induction in the Bigger Picture

Mathematical induction is one part of Proof Techniques II. The topic also includes strong induction and recursive definitions.

Mathematical induction uses one previous case, $P(k)$, to prove $P(k+1)$.
Strong induction allows you to assume all earlier cases up to $k$.
Recursive definitions define a sequence or object using earlier values.

These ideas are connected because recursive structures are often proved correct by induction. For example, if a function or sequence is defined with a base case and a recurrence relation, induction is the natural proof tool.

In computer science, induction helps show that recursive algorithms work correctly. In mathematics, it helps prove formulas and properties that repeat in a predictable pattern. That is why it is a core proof method in discrete mathematics.

Conclusion

Mathematical induction is a powerful way to prove statements about integers, students. Its structure is simple but important: prove a starting case, assume one case, and use that to prove the next. When used carefully, induction can justify formulas, inequalities, divisibility statements, and recursive patterns. It is one of the most useful techniques in discrete mathematics because it turns repetition into proof ✅.

Study Notes

Mathematical induction proves statements for all integers in a range, often $n \ge 0$ or $n \ge 1$.
The two main parts are the base case and the inductive step.
In the inductive step, assume $P(k)$ is true and prove $P(k+1)$ is true.
The assumption $P(k)$ is called the inductive hypothesis.
Induction is useful for sums, inequalities, divisibility, sequences, and recursive patterns.
A correct proof must show the base case and the transition from $k$ to $k+1$.
Induction is closely related to strong induction and recursive definitions in Proof Techniques II.
Common form: if $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for all $k \ge 1$, then $P(n)$ is true for all $n \ge 1$.