# Mathematical Induction (Theory and Examples)

by Dave
(DAVE)—

In this definitive guide to Mathematical Induction, I start from the beginning: precisely what is Mathematical Induction. After working through several examples, I motive the Well-Ordering axiom and examples of it. I then work through examples using Strong Induction. Towards, the end I cover arithmetic and geometric progressions as further examples of using induction. Then, in the end, I prove that Induction, Strong Induction, and the Well-Ordering Axiom are equivalent.

CONTENTS

Have you ever wondered why mathematical induction is a valid proof technique? Or perhaps you are puzzled on the significance of mathematical induction. We cover these inquiries and also hope to help you gain some skill at using induction as well.

We concentrate on examples which demonstrate how to use mathematical induction to prove whether a statement is true for all natural numbers. In addition, the well-ordering axiom and the principle of mathematical induction are proven to be logically equivalent. Moreover, we show that both forms of mathematical induction and the well-ordering axiom are logically equivalent. We also discuss arithmetic and geometric progressions as examples on how to use induction.

## The Principle of Mathematical Induction

In this section, we introduce a powerful method, called mathematical induction, which provides a rigorous means of proving mathematical statements involving sets of positive integers. Mathematical induction is the following statement.

Theorem. If $P$ is a subset of the positive integers with the following properties:

(1) $0 \in P$, and

(2) for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$,

then $P$ is the set of positive integers.

The advantage of mathematical induction is that it gives us a procedure to change “a subset” in the hypothesis to “the set” in the conclusion. Before understanding the foundations of mathematical induction, let’s work through some examples and see how it works.

Example. Prove that for all positive integers $n$, $$\sum_{i=0}^n i =\frac{n(n+1)}{2}.$$

Solution. Let $P$ be the set of positive integers for which this equation is true. Since $0=0=0(1)/2$ we see $0\in P.$ Assume $k\in P.$ Then we find, $$\sum_{i=0}^{k+1} i =\sum_{i=0}^{k} i+(k+1) =\frac{k(k+1)}{2} +(k+1) =\frac{(k+1)(k+2)}{2}$$ which shows $k+1\in P.$ As a result, by mathematical induction $P=\mathbb{N}$ as desired.

## The Well-Ordering Axiom

The well-ordering axiom is the simple claim that: every nonempty set of positive integers has a least element. In the following discussion, this sometimes overlooked and obvious statement will be proven to be logically equivalent to mathematical induction. To be clear, though, it can not be proven using the familiar properties satisfied by the integers under addition and multiplication.

Example. Find the smallest element in each subset of $\mathbb{N}.$

$A=\{n\in \mathbb{N}\mid n \text{ is prime}\}$

$B=\{n\in \mathbb{N} \mid n \text{ is a multiple of 7} \}$

$C=\{n\in \mathbb{N} \mid n=110-7m \text{ for some } m\in \mathbb{Z} \}$

$D=\{n\in \mathbb{N} \mid n=12s+18t \text{ for some } s,t\in \mathbb{Z} \}$

Solution. The smallest prime is 2. The smallest positive multiple of 7 is 7. As $m$ takes on the values $1,2,3,\ldots$, then values of $n$ form the sequence $$93, 76, 59, \ldots, 8, -9 ,\ldots.$$ Hence the smallest element of $C$ is 8. Notice that $12s+18t=6(2s+3t)$ and so elements of $D$ are multiples of $6.$ In fact, $6=(12)(-1)+18(1)$ and so $6$ is in $D.$ Since 6 is the smallest positive multiple of 6, we see that $6$ is the least element of $D.$

## More Examples Using Mathematical Induction

Example. Prove that for all positive integers $n$, $$\sum_{i=1}^n (2i-1)=n^2.$$

Solution. For the base case $n=1$, notice that $(2(1)-1)=1=1^2$. Assume that $k$ is a positive integer and that $\sum_{i=1}^k (2i-1)=k^2.$ Then we find that \begin{align}\sum_{i=1}^{k+1} (2i-1) & = \sum_{i=1}^{k} (2i-1) + \left(2(k+1)-1\right) \\ & = k^2+ \left(2(k+1)-1\right) \\ & =(k+1)^2\end{align} as needed. Hence, by induction, $\sum_{i=1}^n (2i-1)=n^2$ for all positive integers $n$.

Example. Use mathematical induction to show that $$\sum _{i=1}^n (-1)^i i = \frac{(-1)^n(2n+1)-1}{4}$$ for every positive integer $n.$

Solution. For the base case $n=1$, notice that on the left hand side we have $(-1)^1 =1$ and on the right hand side we have $\frac{(-1)(3)-1}{4}=-1$ also. So the base case holds. Assume that $k$ is a positive integer and that $\sum _{i=1}^k (-1)^i i = \frac{(-1)^k(2k+1)-1}{4}.$ Then we find that \begin{align}\sum_{i=1}^{k+1} (-1)^i i & = \sum_{i=1}^{k} (-1)^i i + \left((-1)^{k+1} (k+1)\right) \\ & = \frac{(-1)^k(2k+1)-1}{4} + \left((-1)^{k+1} (k+1)\right) \\ & = \frac{(-1)^{k+1}(2(k+1)+1)-1}{4} \end{align} as needed. Hence, by induction, $\sum _{i=1}^n (-1)^i i = \frac{(-1)^n(2n+1)-1}{4}$ for all positive integers $n$.

Example. Let $x$ be any real number greater than $-1.$ Use mathematical induction to prove that $(1+x)^n\geq 1+n x$ for all positive integers $n.$

Example. In the following, use mathematical induction to prove the inequality. For all $n\geq 1$, $$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\leq 2-\frac{1}{n}.$$

## The Equivalence of Well-Ordering Axiom and Mathematical Induction

On the one hand, the Well-Ordering Axiom seems like an obvious statement, and on the other hand, the Principal of Mathematical Induction is an incredible and useful method of proof.

Theorem. The following statements are equivalent.

(1) Every nonempty set of positive integers has a least element.

(2) If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

Proof. Let $P$ be a subset of positive integers with $0\in P$ and the property that for all positive integers $k$, $k\in P$ implies $k+1\in P.$ Assume, for a contradiction, there exists a nonempty set $S$ containing the positive integers not in $P.$ By the Well-Ordering Axiom, $S$ has a least natural number, $s.$ Since $0\in P$, $s\neq 0.$ Thus there exists a natural number $t$ such that $t+1=s.$ Notice $t\not\in S$ since $t < s.$ Thus $t\in P$ and so $s=t+1\in P.$ This contradiction shows $S$ cannot exist, meaning $P=\mathbb{N}$ as desired. The proof of the converse is left as an exercise.

## Examples Using Mathematical Induction

The next two examples demonstrate how to use mathematical induction. Notice in both examples, we define a set of numbers with the intent of showing that this subset of positive integers is in fact the entire set of positive integers. We do this in two steps. Firstly we verify the base case. Secondly, using an induction hypothesis, we verify the needed implication. The final statement is simply the conclusion that this subset of positive integers $P$ is in fact the entire set of positive integers.

Example. Prove that for all positive integers $n$, \begin{equation} \label{addsumtwo} \sum_{i=0}^n (2i+1)=(n+1)^2. \end{equation}

Solution. Let $P$ be the set of positive integers for which \eqref{addsumtwo} is true, that is $$P=\left\{n\in \mathbb{N} \mid \sum_{i=0}^n (2i+1)=(n+1)^2 \right\}.$$ The basis step is easily verified by $$\sum_{i=0}^0 (2i+1)=1=1^2$$ and so we see $0\in P.$ For an induction hypothesis, assume $k\in P.$ Then $$\sum_{i=0}^k (2i+1)=(k+1)^2$$ is true and thus, $$\sum_{i=0}^{k+1} (2i+1) =\sum_{i=0}^{k} (2i+1)+(2(k+1)+1) =(k+2)^2$$ which shows $k+1\in P.$ By mathematical induction $P=\mathbb{N}$ as desired.

Example. Prove that, for all positive integers $n$, $2^n>n.$

Solution. Let $P$ be the set of all positive integers for which $2^n>n$ is true. Since $2^0=1>0$ is true, $0\in P.$ Assume $k\in P$ and $k>0.$ Then $2^k>k$ is true and since $$2^{k+1}=2^k\cdot 2>k \cdot 2 = k+k> k+1$$ it follows $k+1\in P.$ Thus, for all $k\in P$, $k\in P$ implies $k+1\in P$ is true and so by mathematical induction $P=\mathbb{N}$ as desired.

## Induction Principles

In the hypothesis of mathematical induction, the statement $0\in P$ is called the base case. Mathematical induction is really a collection of principles, for example, the base case may start at $0$, or $1$, or $2$, etc. instead of $0.$ In each of these scenarios the goal is to prove a collection of statements is true, for all $n$ greater than some initial value which must be verified (base case). For example, while $n!>n$ is not true for $n=0, 1, 2$, it is true for all $n\geq 3.$ So our base case is $n=3.$ Let’s prove that $n!>n$ for all $n\geq 3.$ Since $3!=1\cdot 2\cdot 3=6>3$ we see that the base case holds. Now assume that for some positive integer $k$ greater than 3, that $k!>k.$ Then wee see that \begin{equation} \label{factind} (k+1)!=k!(k+1)>k(k+1)>k+1. \end{equation} Therefore, by mathematical induction, $n!>n$ for all $n\geq 3.$

## The Strong Form of Induction

There is another variant of induction (namely, strong induction) which has a stronger induction hypothesis. While the hypothesis is stronger, both statements are actually logically equivalent to each other, as the next theorem demonstrates.

Theorem. The following statements are equivalent.

(1) If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

(2) If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $0,1,\ldots , k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

Proof. Let $S$ be a set of positive integers with $0\in S$ and the property, for all positive integers $k$, $0,1,2,\ldots,k\in S$ implies $k+1\in S.$ Let $P$ be the set of positive integers for which $0,2, \ldots, n\in S$ is true. Notice $0\in P$ since $0\in S.$ Assume $k\in P.$ Then $0,1,2, \ldots, k\in S.$ Thus $0,1,2,3,\ldots , k , k+1\in S$ meaning $k+1\in P.$ Hence, $P=\mathbb{N}.$ By definition of $P$, $S=\mathbb{N}$ as desired. The proof of the converse is left as an exercise.

### Lucas numbers

To illustrate the strong form of induction we will discuss the Lucas numbers. Numbers in the sequence $1, 3, 4, 7, 11, 18, \ldots$ are called Lucas numbers. They are defined inductively by, $L_1=1$, $L_2=3$, $L_n=L_{n-1}+L_{n-2}$ for all $n\geq 3.$

Example. Prove that for all positive integers $n$, \begin{equation} \label{lussevenfour} L_n < \left(\frac{7}{4}\right)^n. \end{equation}

Solution. For the basis step notice that $$L_1=1< \left(\frac{7}{4}\right)^1=\frac{7}{4}.$$ For a strong induction hypothesis, we assume that \eqref{lussevenfour} holds true for $n=1, \dots, k-1.$ Then we find, \begin{align} L_k =L_{k-1}+L_{k-2} & < \left(\frac{7}{4}\right)^{k-1}+\left(\frac{7}{4}\right)^{k-2} \\ & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}+1\right) \\ & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{11}{4}\right) \\ & < \left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}\right)^{2} \\& =\left(\frac{7}{4}\right)^{k}. \end{align} Because the inequality is true for $n=k$ whenever it is true for the integers $1, 2, \dots, k-1$, we conclude, by Strong Induction that, $L_n < (7/4)^n$ for all $n\geq 1.$

## The Equivalence of the Well-Ordering Axiom and the Strong Form of Mathematical Induction

In the above statement, we have proven that the Well-Ordering Axiom and the Principle of Mathematical Induction are logically equivalent. Similarly, we can now prove that the Well-Ordering Axiom and the Strong Form of Mathematical Induction are logically equivalent. It should be pointed out that since both principles of mathematical induction are logically equivalent to the Well-Ordering Axiom, then the Principle of Mathematical Induction and the Strong Form of Mathematical Induction are also logically equivalent.

Theorem. The following statements are equivalent.

(1) If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $0,1,\ldots , k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

(2) Every nonempty set of positive integers has a least element.

Proof. Assume, for a contradiction, there exists a nonempty set of positive integers $S$ with no least element. Let $P$ be the set of positive integers for which $n\notin S$ is true. Because $0$ is the least element of all positive integers, $0\notin S$ and so $0\in P.$ Assume $0,1,\ldots ,k\in P.$ If $k+1\in S$ then $k+1$ is the least element of $S.$ However, $S$ has no least element and thus $k+1\notin S.$ Thus, $k+1\in P$ and so by Strong Induction we have $P=\mathbb{N}.$ This contradiction shows $S$ can not exist. Therefore, $S=\mathbb{N}.$ The proof of the converse is left as an exercise.

## Basis Step Required

In any proof by induction, we must not forget to show that $0$ is in $P.$ Even if we show that the truth of $k$ in $P$ implies that $k+1$ is in $P$, if $0$ is not in $P,$ then we cannot conclude that $P$ is the set of positive integers. For example, let $P$ be the set of all positive integers that satisfies: \begin{equation} \label{falseq} n+(n+1)=2n. \end{equation} Suppose $k$ satisfies, \eqref{falseq}. Using this we have \begin{equation} (k+1) + (k+2) = k + (k+1) + 2 = 2k+2 = 2(k+1) \end{equation} and thus $k+1$ also satisfies \eqref{falseq}.

So, if $0$ satisfies \eqref{falseq} then, it would follow that \eqref{falseq} is true for all positive integers $n.$ However, $0$ does not satisfy \eqref{falseq}. In fact, obviously, \eqref{falseq} is false for all positive integers $n.$ We conclude that the basis step is a necessary part in any proof by mathematical induction.

## Arithmetic and Geometric Progressions

In addition, we will demonstrate the usefulness of mathematical induction by providing rigorous proofs for the arithmetic and geometric progression formulas.

Definition. A sequence of the form $a, a+d, a+2d, \ldots, a+nd, \ldots$ where $a,d\in \mathbb{R}$ is called an arithmetic progression.

Example. Let $a,d\in \mathbb{R}.$ Prove that for every positive integer $n$, that \begin{equation} \label{arithprog} a+(a+d)+(a+2d)+\cdots + (a+nd) =\frac{(n+1)(2a+nd)}{2}. \end{equation}

Solution. Let $P$ be the set of positive integers for which \eqref{arithprog} holds. Since $$a+(a+d)=[(1+1)(2a+d)]/2$$ we see that $1\in P.$ Assume $k\in P.$ We find \begin{align} & a+(a+d)+\cdots + (a+kd) + (a+(k+1) d) \\ & \qquad\qquad = \frac{(k+1)(2a+kd)}{2} + (a+(k+1) d) \\ & \qquad\qquad = \frac{(k+1)(2a+kd)+ 2(a+(k+1) d)}{2} \\ & \qquad\qquad = \frac{(k+2)(2a+(k+1)d)}{2} \end{align} Therefore, $k+1\in P$ and thus \eqref{arithprog} holds for $n\geq 1.$

Definition. A sequence of the form $a, ar, ar^2, \ldots, a r^n, \ldots$ where $a,r\in \mathbb{R}$ and $r\neq 1$ is called a geometric progression.

Example. Let $a,r\in \mathbb{R}$ and suppose $r\neq 1.$ Prove that, each positive integer $n$, that \begin{equation} \label{geopro} a+ar +ar^2+\cdots +a r^n = a\left(\frac{r^{n+1}-1}{r-1}\right). \end{equation}

Solution. Let $P$ be the set of positive integers for which \eqref{geopro} holds. Since $a+ar=a (r^2-1)/(r-1)$, we see that $1\in P.$ Assume $k\in P.$ We find \begin{align} a+ar +ar^2+\cdots +a r^k+a r^{k+1} & =a\left(\frac{r^{k+1}-1}{r-1}\right)+a r^{k+1} \\ & =\frac{a r^{k+1}-a+(r-1)a r^{k+1} }{r-1} \\ & = a\left(\frac{r^{k+2}-1}{r-1}\right). \end{align} Therefore, $k+1\in P$ and thus \eqref{geopro} holds for $n\geq 1.$

## Exercises on Mathematical Induction (Part A)

In the following, use a form of mathematical induction to solve each exercise.

Exercise. Prove that, for all positive integers $n$, $$\sum _{k=1}^n k^2=\frac{n(2n+1)(n+1)}{6}.$$

Exercise. Prove that, for all positive integers $n$, $$\sum _{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2.$$

Exercise. Prove that, for all positive integers $n$, $$\sum _{j=1}^n (-1)^{j-1}j^2=(-1)^{n-1}\frac{n(n+1)}{2}.$$

Exercise. Prove that, for all positive integers $n$, $$\sum _{j=1}^n j\cdot j! =(n+1)!-1.$$

Exercise. Use mathematical induction to show that $$\sum _{k=1}^n (-1)^kk=\frac{(-1)^n(2n+1)-1}{4}$$ for every positive integer $n.$

Exercise. Use mathematical induction to show that the sum of the first $n$ odd cubes is $n^2\left(2n^2-1\right).$

Exercise. Use mathematical induction to prove that $2^n < n!$ for $n\geq 4.$

## Exercises on Mathematical Induction (Part B)

In the following, use a form of mathematical induction to solve each exercise.

Exercise. Use mathematical induction to prove that $3^n>3n-1$ for every positive integer $n.$

Exercise. Use mathematical induction to prove that $2^{n-1}>n$ for all positive integers $n\geq 3.$

Exercise. Use mathematical induction to prove that $2^n > n^2$ for $n>4.$

Exercise. In the following, use the strong form of mathematical induction to establish that for all $n\geq 1,$ $$a^n-1=(a-1)\left(a^{n-1}+a^{n-2}+a^{n-3}+\cdots+a+1\right).$$

Exercise. Use mathematical induction to show that $$2\cdot 6\cdot 10\cdot 14\cdot \cdot \cdot \cdot \cdot (4n-2)=\frac{(2n)!}{n!}$$ for every positive integer $n.$

Exercise. Show that any amount of postage that is an integer number of cents greater than 53 cents can be formed using just 7-cent and 10-cent stamps.

Exercise. Let $x$ be any real number greater than $-1.$ Use mathematical induction to prove that $(1+x)^n\geq 1+n x$ for all positive integers $n.$

Exercise. Use mathematical induction to prove that $x-y$ is a factor of $x^n-y^n,$ where $x$ and $y$ are variables.

Exercise. In the following, use mathematical induction to prove the inequality.

(1) For all $n\geq 1$, $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\leq 2-\frac{1}{n}.$

(2) For all $n\geq 1$, $\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{n}{2^n}\leq 2-\frac{n+2}{2^n}.$

Exercise. Use mathematical induction to prove that $2^n > n^2$ for $n>4.$

Exercise. Use mathematical induction to show that for every positive integer $n,$ $$\sum _{i=1}^n 2^k=2^{n+1}-2.$$

Exercise. In the following, use mathematical induction to solve the problem.

(1) You have a supply of $32$ cent stamps and $21$ cent stamps. You need to mail a package which requires $1.48$ dollars in postage. How many of each type of stamp should you use?

(2) Show that any amount of postage that is an integer number of cents greater than 53 cents can be formed using just 7-cent and 10-cent stamps.

Exercise. Prove $n < 2^n$ whenever $n$ is a positive integer.