## Section5.1Mathematical Induction

Suppose we wish to show that

\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}

for any natural number $n\text{.}$ This formula is easily verified for small numbers such as $n = 1\text{,}$ $2\text{,}$ $3\text{,}$ or $4\text{,}$ but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.

Suppose we have verified the equation for the first $n$ cases. We will attempt to show that we can generate the formula for the $(n + 1)$th case from this knowledge. The formula is true for $n = 1$ since

\begin{equation*} 1 = \frac{1(1 + 1)}{2}\text{.} \end{equation*}

If we have verified the first $n$ cases, then

\begin{align*} 1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\ & = \frac{n^2 + 3n + 2}{2}\\ & = \frac{(n + 1)[(n + 1) + 1]}{2}\text{.} \end{align*}

This is exactly the formula for the $(n + 1)$th case.

This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset $S$ of the positive integers ${\mathbb N}$ on a case-by-case basis, an impossible task if $S$ is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.

For all integers $n \geq 3\text{,}$ $2^n \gt n + 4\text{.}$ Since

\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7\text{,} \end{equation*}

the statement is true for $n_0 = 3\text{.}$ Assume that $2^k \gt k + 4$ for $k \geq 3\text{.}$ Then $2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}$ But

\begin{equation*} 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \end{equation*}

since $k$ is positive. Hence, by induction, the statement holds for all integers $n \geq 3\text{.}$

Every integer $10^{n + 1} + 3 \cdot 10^n + 5$ is divisible by $9$ for $n \in {\mathbb N}\text{.}$ For $n = 1\text{,}$

\begin{equation*} 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \end{equation*}

is divisible by $9\text{.}$ Suppose that $10^{k + 1} + 3 \cdot 10^k + 5$ is divisible by $9$ for $k \geq 1\text{.}$ Then

\begin{align*} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\ & = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{align*}

is divisible by $9\text{.}$

A nonempty subset $S$ of ${\mathbb Z}$ is well-ordered if $S$ contains a least element. Notice that the set ${\mathbb Z}$ is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

You can find the proof of Theorem 5.1.5 in Subsection A.2

Induction can also be very useful in formulating definitions. For instance, there are two ways to define $n!\text{,}$ the factorial of a positive integer $n\text{.}$

• The explicit definition: $n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}$

• The inductive or recursive definition: $1! = 1$ and $n! = n(n - 1)!$ for $n \gt 1\text{.}$

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.

### Exercises5.1.1Exercises

###### 1.

Prove that

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}

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

###### 2.

Prove that

\begin{equation*} 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n + 1)^2}{4} \end{equation*}

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

###### 3.

Prove that $n! \gt 2^n$ for $n \geq 4\text{.}$

###### 4.

Prove that

\begin{equation*} x + 4x + 7x + \cdots + (3n - 2)x = \frac{n(3n - 1)x}{2} \end{equation*}

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

###### 5.

Prove that $10^{n + 1} + 10^n + 1$ is divisible by $3$ for $n \in {\mathbb N}\text{.}$

###### 6.

Prove that $4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5$ is divisible by $99$ for $n \in {\mathbb N}\text{.}$

###### 7.

Use induction to prove that $1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1$ for $n \in {\mathbb N}\text{.}$

###### 8.

Prove that

\begin{equation*} \frac{1}{2}+ \frac{1}{6} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1} \end{equation*}

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

###### 9.

If $x$ is a nonnegative real number, then show that $(1 + x)^n - 1 \geq nx$ for $n = 0, 1, 2, \ldots\text{.}$

###### 10.Power Sets.

Let $X$ be a set. Define the power set of $X\text{,}$ denoted ${\mathcal P}(X)\text{,}$ to be the set of all subsets of $X\text{.}$ For example,

\begin{equation*} {\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}\text{.} \end{equation*}

For every positive integer $n\text{,}$ show that a set with exactly $n$ elements has a power set with exactly $2^n$ elements.