1.1: Induction and Well-Ordering

Learning Objectives

In this section, we'll seek to answer the questions:

• What is the Well-Ordering Principle?
• What is mathematical induction, and how can we use it to prove statements about \(\mathbb{N}\)

In this section we will assume the basic algebraic/arithmetic properties of the integers such as closure under addition, subtraction, and multiplication, most of which we will formalize via axioms in subsequent sections. Axiom 1.1.1 : Well-Ordering Principle formalizes the familiar notion that nonempty subsets of the positive integers have a smallest element, which will be used repeatedly throughout the text. We then explore a closely related idea, mathematical induction, via an example and exercises.

Definition: Natural Numbers

The collection of natural numbers is denoted by \(\mathbb{N}\), and is the set,

\(\mathbb{N}=\{ 1 \text{,}2\text{,}3\text{,} \ldots \}\).

By \(\mathbb{N}_0\) we mean the set \(\mathbb{N} \cup {0}=\{ 0\text{,}1 \text{,}2\text{,}3\text{,} \ldots\}\).

In some sense, the fundamental properties of \(\mathbb{N}\) are (a) there is a smallest natural number, and (b) there is always a next natural numberIn fact, one can build a model of \(\mathbb{N}\) with set theory and the Peano axioms, which utilize the notion of a successor--the next natural number.). A consequence of the Peano postulates is the well-ordering principle, which we state as an axiom.

Axiom 1.1.1 : Well-Ordering Principle

Every nonempty subset of \(\mathbb{N}_0\) contains a least (smallest) element under the usual ordering, \(\leq\).

Note

Our word choice is suggestive. In fact, other orderings do exist, and while the set of no\(\mathbb{N}\)egative real numbers RR does not satisfy the well-ordering principle under the usual ordering \(\leq\), the Well Ordering Axiom asserts that there exists a well ordering on any set, including R.R. Accepting this axiom is equivalent to accepting the axiom of choice.

The Well-Ordering Principle is useful for producing smallest elements of nonempty subsets defined to have certain properties, as the following example demonstrates.

Exploration 1.1.1

In this exploration, we investigate polynomials with real coefficients, as well as their degrees. We will define these terms more formally in Definition: Polynomial, but for now you may use your intuition from previous courses in algebra.

Let \(S\) be the set of all polynomials \(f\) in the variable \(x\) with real coefficients such that \(f(2)=f(−2)=0\) and \(f(0)=−4\).

1. Give an example of an \(f\in S\) and \(g\notin S\).
2. Let \(D=\{deg\; f : \; f\in S\}\) be the set of possible degrees of polynomials in \(S\). Show that \(D\neq \varnothing\) and \(D\subseteq \mathbb{N}_0\).
3. Apply the Well-Ordering Principle to argue that \(D\) has a least element. To what does this correspond in \(S\)?

We will use this principle throughout the text, next in Theorem 1.2.4.

Figure 1.1.1 : A suspect use of the Well-Ordering Principle.

Definition: Integer

The set of integers consists of the positive and negative natural numbers, together with zero, and is denoted by \(\mathbb{Z}\):

\(\mathbb{Z}=\{ \ldots \; ,−3\; ,−2\; ,−1\; ,0\; ,1\; ,2\; ,3\; , \ldots \}\).

Mathematical Induction

Let \(P(m)\) be a statement about the natural number \(m\). Let \(k_0\in \ N\) be such that the statement \(P(k_0)\) is true (the base case), and suppose there is an \(n\geq k_0\) such that for all \(k\) satisfying \(k_0 \leq k \leq n\), \(P(k)\) is true (the inductive hypothesis). Then \(P(n+1)\) is true, and thus \(P(m)\) is true for all \(m\geq k_0\) (the inductive step).

Note

Sample statements could include “\(m\) is really interesting” or “\(3m^2+m+2\) is even”.

Mathematical induction is like climbing an infinite staircase. The base case tells us that we can take a first step on the staircase (\(k_0\)). In the inductive hypothesis, we assume we can take all the steps up to a certain height (\(\mathbb{N}\)). In the inductive step, we prove that this allows us to take the \((n+1)\) st step.

Thus, if we can take step \(k_0\), we can (by the inductive step) take step \(k_0+1\). And since we can take step \(k_0+1\),we can (again by the inductive step) take step \(k_0+2\).And so on, forever (or, if the notion of actual infinity makes you uncomfortable, as far as we want to go).

Example 1.1.1

For all \(n\geq 1\),

\(1+2+3+\ldots +n=\dfrac{n(n+1)}{2}\).

Proof. Base case: When \(n=1\), the equation \(1=\dfrac{1\cdot (1+1)}{2}\) is true.

Solution

Inductive Hypothesis: Assume that there exists a \(n\) such that whenever \(k \leq n\), the equation

\[1+2+3+\ldots +k=\dfrac{k(k+1)}{2} \label{\PageIndex{1}}\]

is true.

Inductive Step: Our goal is to show that \(P(n+1)\) is true. That is, we wish to establish that

\[1+2+3+\ldots +n+(n+1)=\dfrac{(n+1)((n+1)+1)}{2}\label{\PageIndex{2}}\]

We begin on the left-hand side of \( \ref{\PageIndex{1}}\) where we may apply the inductive hypothesis to see that

\[1+2+3+\ldots +n+(n+1)=\left[\dfrac{n(n+1)}{2}\right]+(n+1).\label{\PageIndex{3}}\]

Through the use of straightforward algebra, the right-hand side becomes

\[\dfrac{n(n+1)}{2}+\dfrac{2(n+1)}{2}=\dfrac{n(n+1)+2(n+1)}{2}=\dfrac{(n+1)(n+2)}{2}. \label{\PageIndex{4}}\]

Putting \(\ref{\PageIndex{3}}\) and \(\ref{\PageIndex{4}}\) together, we obtain

\(1+2+3+\ldots +n+(n+1)=\dfrac{(n+1)((n+1)+1)}{2},\)

which is exactly the goal we stated in \(\ref{\PageIndex{2}}\).

We conclude with opportunities to practice induction.

Theorem 1.1.1

For all \(k\geq 1\), \(k\geq 1\), \(3^k>k\).

Theorem 1.1.2

Prove that the sum of the first \(\mathbb{N}\) cubes is \(\dfrac{n^2(n+1)^2}{4}\). That is,

\(1^3+2^3+3^3+\ldots +n^3=\dfrac{n^2(n+1)^2}{4}\).

Theorem 1.1.3

(Bernoulli's Inequality). Given a real number \(b>−1\), \(b>−1\), \((1+b)^n\geq 1+bn\) for all \(n\in \mathbb{N}_0\).