Mathematical Induction

The Need for Induction

Many statements in number theory concern all natural numbers. For example, one may wish to prove that

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

for every $n\in\mathbb{N}$ .

It is not enough to check the formula for several values of $n$ . Checking

n=1,2,3,4,5

shows only that the formula holds in those cases. A proof must show that it holds for every natural number.

Mathematical induction is the standard method for proving such statements.

The Principle of Induction

The principle of mathematical induction says the following.

Let $P(n)$ be a statement depending on a natural number $n$ . Suppose that:

$P(1)$ is true.
For every $k\in\mathbb{N}$ , if $P(k)$ is true, then $P(k+1)$ is true.

Then $P(n)$ is true for every $n\in\mathbb{N}$ .

The first step is called the base case. The second step is called the induction step.

The assumption that $P(k)$ is true is called the induction hypothesis.

Why Induction Works

Induction works because the natural numbers are built by repeatedly taking successors.

If $P(1)$ is true, and truth passes from each integer $k$ to its successor $k+1$ , then

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

No natural number is skipped. Every natural number is eventually reached by starting at $1$ and applying the successor operation finitely many times.

Thus induction is a formal expression of the recursive structure of $\mathbb{N}$ .

A First Example

We prove that

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

for every $n\in\mathbb{N}$ .

For $n=1$ , the left-hand side is $1$ , and the right-hand side is

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

Thus the base case holds.

Now assume that the formula holds for some $k\in\mathbb{N}$ . That is, assume

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

We must prove the corresponding formula for $k+1$ . Using the induction hypothesis,

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

Factoring $k+1$ , we get

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

Hence

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

This is exactly the desired formula with $n=k+1$ . Therefore the statement holds for all $n\in\mathbb{N}$ .

Induction Starting at Other Values

Induction need not always begin at $1$ . Sometimes a statement is meant to hold for all integers $n\ge n_0$ , where $n_0$ is a fixed integer.

In that case, one proves:

$P(n_0)$ is true.
For every $k\ge n_0$ , if $P(k)$ is true, then $P(k+1)$ is true.

Then $P(n)$ is true for every integer $n\ge n_0$ .

For example, many inequalities are false for small values of $n$ but true once $n$ is sufficiently large.

Induction and Inequalities

Induction is often used to prove inequalities. As an example, we prove that

2^n\ge n+1

for every $n\in\mathbb{N}_0$ .

For $n=0$ ,

2^0=1

and

0+1=1.

So the base case holds.

Assume now that

2^k\ge k+1.

Then

2^{k+1}=2\cdot2^k\ge 2(k+1)=2k+2.

Since

2k+2\ge k+2

for $k\ge0$ , it follows that

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

This is the desired statement for $k+1$ . Hence

2^n\ge n+1

for every $n\in\mathbb{N}_0$ .

Common Mistakes

A proof by induction must contain both a base case and an induction step.

If the base case is omitted, the argument has no starting point. It is like a ladder whose first rung is missing.

If the induction step is omitted, the argument proves only one case.

Another common mistake is to assume what must be proved. In the induction step, one may assume $P(k)$ , but one must prove $P(k+1)$ . One may not simply assume $P(k+1)$ .

Role in Number Theory

Induction is one of the basic proof methods of number theory. It is used to prove formulas, divisibility statements, inequalities, recurrence relations, and structural facts about the integers.

For example, induction can prove that every integer $n\ge2$ has a prime divisor. It can also prove the existence part of unique factorization, once the necessary divisibility facts are established.

The method is powerful because many arithmetic objects are recursive. Natural numbers arise by succession, sums arise by adding one term at a time, and many algorithms proceed by reducing a problem to a smaller one. Induction turns this recursive structure into proof.