Mathematical Induction

Mathematical induction is the result of taking advantage of special properties of the natural numbers. However, one can establish axioms for what constitutes “the natural numbers.” There are a few approaches to defining the natural numbers, but I find the “Peano axioms” to be the most intuitive. In this page, I omit several details because the overall purpose is not to construct the natural numbers, but to understand the Principal of Induction at a slightly different perspective then you may have seen and review some facts we should know.

Definition: Let $N$ be a nonempty set (called the underlying set), $1 \in N$ (called the distinguished element of $N$ ), and $s:N \rightarrow N$ be a function (which will be referred to as the successor function). We say the triple $(N,s,1)$ is a Peano system if:

For all $n \in N$ , $s(n)\not=1$ .
For all $m,n \in N$ , if $s(n)=s(m)$ , then $m=n$ .
If $M\subseteq N$ such that $1 \in M$ and $m \in M$ implies $s(m) \in M$ , then $M=N$ .

We refer to the third axiom as the “axiom of induction.” Two facts can be established quickly:

$s$ is a bijection from $N$ onto $N\setminus\{1\}$

Proof: By (1), $1 \not \in s(N)$ . By (2), $s$ is injective, thus we only need to show surjectivity. Set $M=s(N)\cup\{1\}$ . Now, clearly, $1 \in M$ . If $n \in M$ , then $n \in N$ since $\{1\}$ and $s(N)$ are both subsets of $N$ , thus $s(n) \in M$ . Therefore, by (3), $M=N$ .

For all $n \in N$ , $s(n)\not=n$ .

Proof: Let $M=\{n \in N \;:\; s(n)\not=n\}$ . By (1), $1 \in M$ . By (2), if $n \in M$ , i.e. $s(n)\not=n$ , then $s(s(n))\not=s(n)$ (applying the contrapositive), thus $s(n) \in M$ . Therefore, by (3), $M=N$ , i.e. $s(n)\not=n$ for all $n \in N$ .

Using the successor function, one can prove the existence of a unique notion of addition and multiplication on $N$ satisfying all of the many properties we are familiar with: For all $a,b,c \in N$ ,

$\begin{align*} (a+b)+c&=a+(b+c) \\ a+b&=b+a \\ (ab)c&=a(bc) \\ ab&=ba \\ a\cdot 1 &= a \\ a(b+c)&=ab+ac \\ (a+b)c&=ac+bc \end{align*}$

And for any $a,b \in N$ , only one of the following conditions hold:

$a=b$
There exists $n \in N$ such that $a=b+n$
There exists $n \in N$ such that $b=a+n$

We see that $(\mathbb{N},1,s)$ where $s: \mathbb{N} \rightarrow \mathbb{N}$ defined by $s(n)=n+1$ satisfies the Peano axioms. The axiom of induction plays an essential role in establishing the validity of “proof by induction” as a method of proof. In fact, using the Peano axioms, one can prove that “proof by induction” is valid.

The Principle of Mathematical Induction. Let $(N,s,1)$ be a Peano system and let $P(n)$ be a property associated to the element $n \in N$ . If $P(1)$ is true and $P(n)$ is true implies $P(s(n))$ is true for all $n \in N$ , then $P(n)$ is true for all $n \in N$ .

Proof: Let $M=\{n \in N\;:\; P(n)\text{ is true}\}$ . By $P(1)$ is true, $1 \in M$ . By $P(n)$ is true implies $P(s(n)$ is true, we have $n \in M$ implies $s(n) \in M$ . Therefore, by the axiom of induction, $M=N$ , i.e. $P(n)$ is true for all $n \in N$ .

There are two variations often discussed:

The Principle of Mathematical Induction: Let $(N,s,1)$ be a Peano system and let $P(n)$ be a property associated to the element $n \in N$ . If for some $m \in M$ , $P(m)$ is true and $P(n)$ is true implies $P(s(n))$ is true for all $n \geq m$ , then $P(n)$ is true for all $n \in N$ .

The Strong Principle of Induction: Let $(N,s,1)$ be a Peano system and let $P(n)$ be a property associated to the element $n \in N$ and fix $k \in N$ . If for each $m \in N$ , $P(i)$ is true for $k\leq i<m$ implies $P(m)$ is true, then $P(n)$ is true for all $n\geq k$ .

Exercise: Prove that $2^n>n$ for all $n \in \mathbb{N}$ .

Proof: Let $P(n)$ be the property that $2^n>n$ . It is clear $2^1>1$ , i.e. $P(1)$ is true. Suppose $2^k>k$ , then

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

Therefore, $2^n>n$ for all $n \in \mathbb{N}$ .

Exercise: Prove that $\sum\limits_{i=1}^n (2i-1)=n^2$ for all $n \in \mathbb{N}$ .

Proof: Let $P(n)$ be the property that $\sum\limits_{i=1}^n (2i-1)=n^2$ . It is clear $2(1)-1=1^2$ , i.e. $P(1)$ is true. Suppose $\sum\limits_{i=1}^k (2i-1)=k^2$ , then

$\sum\limits_{i=1}^{k+1} (2i-1)= \sum\limits_{i=1}^k (2i-1) + (2(k+1)-1)=k^2 +2k+1 = (k+1)^2$

Therefore, $P(n)$ is true for all $n \in \mathbb{N}$ .

Exercise: Show that $n$ distinct points on the real line divides the real into $n+1$ intervals.

Proof: Choosing distinct points on the real line corresponds to choosing a real number. Let $r \in \mathbb{R}$ , then the real line is split into two intervals $(-\infty, r)$ and $(r,\infty)$ . Assume that $k$ distinct points divide the real line into $k+1$ intervals. Let $r_1, r_2, \dots, r_{k+1}$ be distinct points in $\mathbb{R}$ such that $r_1<r_2<\cdots<r_{k+1}$ . By the inductive hypothesis, $r_1,\dots, r_k$ divide the real line into $k+1$ intervals $I_1, \dots, I_{k+1}$ where $I_{k+1} = (r_k,\infty)$ . Then, $r_{k+1}$ splits $I_{k+1}$ into two intervals $I'_{k+1}=(r_k,r_{k+1}$ and $I_{k+2}=(r_{k+1},\infty)$ . Therefore, $k+1$ points splits the real line into $k+2$ intervals.

Note: We are applying induction that any point in an interval divides any interval into two subintervals since $\mathbb{R}$ is itself an interval.

Exercise: Prove that $\frac{d^n}{dx^n}(e^{cx})=c^ne^{cx}$ .