# Well Ordering Principle

The well ordering principle relies on the fact that the set $$\mathbb{Z^{+}}$$ is well-ordered and states that every non-empty subset of positive integers has a least element.

More formally, let $$S \subseteq \mathbb{Z^{+}}.$$ Then $$S$$ has a least element, i.e. there is an $$m \in S$$ such that $$m \le n$$ for all $$n \in S.$$

The well ordering principle is often used in proofs by contradiction to show that a predicate $$P\left( n \right)$$ is true for all $$n \in \mathbb{N}.$$

A standard way of such proof looks as follows:

• Suppose $$P\left( n \right)$$ is false, that is, $$\exists n,$$ $$\neg P\left( n \right).$$
• Define the set of counterexamples $$C = \left\{ {n \in N:\neg P\left( n \right)} \right\}.$$
• Assume $$C$$ is non-empty to derive a contradiction.
• By the well ordering principle, there exists a least element $$m \in C.$$
• Derive a contradiction either by proving $\forall i \lt m,P\left( i \right) \Rightarrow P\left( m \right),$ which contradicts to $$\neg P\left( m \right),$$ or by proving $\neg P\left( m \right) \Rightarrow \exists i \lt m,\neg P\left( i \right),$ which contradicts the fact that $$P\left( i \right)$$ is true for all $$i \lt m.$$
• Conclude that $$C$$ must be empty, that is, no counterexamples exist, and hence, $$P\left( n \right)$$ is true for all $$n \in \mathbb{N}.$$

The well ordering principle and the principle of mathematical induction are logically equivalent.

Consider an example of a proof using the well ordering principle. Let’s prove the following finite series formula

${\sum\limits_{i = 1}^n {{i^3}} }={ {1^3} + {2^3} + {3^3} + \ldots + {n^3} }={ \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}.}$

The predicate $$P\left( n \right)$$ here means that the sum of the cubes of the first $$n$$ natural numbers is $$\large{\frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}}\normalsize.$$

Suppose by contradiction that $$P\left( n \right)$$ is false. The set $$C$$ of counterexamples is defined as

${C = \left\{ {n \in \mathbb{N} \mid \sum\limits_{i = 0}^n {{i^3}} \ne \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}} \right\}.}$

We assume that $$C$$ is non-empty. Then, according to the well ordering principle, there must exist a least element $$m$$ in $$C.$$ The predicate $$P\left( m \right)$$ for the number $$m$$ is false, that is

$\sum\limits_{i = 1}^m {{i^3}} \ne \frac{{{m^2}{{\left( {m + 1} \right)}^2}}}{4}.$

Note that $$m \gt 1$$ since $$P\left( 1 \right)$$ is true:

${LHS = \sum\limits_{i = 1}^1 {{i^3}} = {1^3} = 1;\;\;}\kern0pt{ RHS = \frac{{{1^2}{{\left( {1 + 1} \right)}^2}}}{4} = \frac{4}{4} = 1.}\;\;\Rightarrow {LHS = RHS.}$

For all $$1 \le i \lt m,$$ the predicate $$P\left( i \right)$$ is true. So, for $$i = m-1$$ we have

$\sum\limits_{i = 1}^{m – 1} {{i^3}} = \frac{{{{\left( {m – 1} \right)}^2}{m^2}}}{4}.$

By adding $$m^3$$ to both sides of the last equation we obtain

${\sum\limits_{i = 1}^m {{i^3}} }={ \frac{{{{\left( {m – 1} \right)}^2}{m^2}}}{4} + {m^3} }={ \frac{{\left( {{m^2} – 2m + 1} \right){m^2}}}{4} + {m^3} }={ \frac{{{m^4} – 2{m^3} + {m^2} + 4{m^3}}}{4} }={ \frac{{{m^4} + 2{m^3} + {m^2}}}{4} }={ \frac{{{m^2}\left( {{m^2} + 2m + 1} \right)}}{4} }={ \frac{{{m^2}{{\left( {m + 1} \right)}^2}}}{4}.}$

which means that $$P\left( m \right)$$ is true. But this contradicts the fact that $$m$$ is the least element in $$C.$$ Hence, our assumption that the set $$C$$ is non-empty is wrong. Thus, the finite series formula holds for all $$n \in \mathbb{N}.$$

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Prove the formula for the sum of the first $$n$$ odd natural numbers: ${\sum\limits_{i = 1}^n {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2n – 1} \right) }={ {n^2}.}$

### Example 2

Prove the formula for the sum of the first $$n$$ even natural numbers: ${\sum\limits_{i = 1}^n {{2i}} }={ 2 + 4 + 6 + \ldots + 2n }={ n\left({n+1}\right).}$

### Example 3

Show that $$n^5 – n$$ is divisible by $$5$$ for any $$n \in \mathbb{N}.$$

### Example 4

Show that $$4^n – 1$$ is divisible by $$3$$ for any $$n \in \mathbb{N}.$$

### Example 5

Prove that for all natural numbers $\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{n}{{n + 1}}.$

### Example 6

Prove by well ordering principle that $\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{{n + 1}}{{2n}}$ for $$n \ge 2.$$

### Example 1.

Prove the formula for the sum of the first $$n$$ odd natural numbers: ${\sum\limits_{i = 1}^n {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2n – 1} \right) }={ {n^2}.}$

Solution.

By following the general pattern for well ordering proof, we suppose that the formula is false for certain $$n.$$ We collect all such numbers in a set $$C:$$

$C = \left\{ {n \in \mathbb{N} \mid \sum\limits_{i = 1}^n {\left( {2i – 1} \right)} \ne {n^2}} \right\}.$

By the well ordering principle, there is a least element $$m$$ in set $$C.$$ Notice that $$m \gt 1$$ since the formula is true for $$n = 1:$$

${LHS = \sum\limits_{i = 1}^1 {\left( {2i – 1} \right)} = 1;\;\;}\kern0pt{ RHS = {1^2} = 1,}\;\; \Rightarrow {LHS = RHS.}$

The summation formula is also true for all $$1\le i \lt m,$$ so for $$i = m-1$$ we get

${\sum\limits_{i = 1}^{m – 1} {\left( {2i – 1} \right)} }={ 1 + 3 + 5 + \ldots + \left( {2m – 3} \right) }={ {\left( {m – 1} \right)^2}.}$

Add the next term $$2m – 1$$ to both sides of the equation. This yields

$\require{cancel}{\sum\limits_{i = 1}^m {\left( {2i – 1} \right)} }={ {\left( {m – 1} \right)^2} + 2m – 1 }={ {m^2} – \cancel{2m} +\cancel{1} + \cancel{2m} – \cancel{1} }={ {m^2}}.$

The last equation shows that the summation formula is also true for the number $$m,$$ which contradicts the assumption. Hence, the set of counterexamples $$C$$ is empty and the given formula holds for all $$n \in \mathbb{N}.$$

### Example 2.

Prove the formula for the sum of the first $$n$$ even natural numbers: ${\sum\limits_{i = 1}^n {{2i}} }={ 2 + 4 + 6 + \ldots + 2n }={ n\left({n+1}\right).}$

Solution.

We prove by well ordering. Let $$P\left( n \right)$$ be the assertion that the summation formula is true for a number $$n$$ where $$n \in \mathbb{N}$$. By contradiction, we assume that there are some values of $$n$$ for which this formula is false. We collect all such values of $$n$$ in a set $$C,$$ so

$C = \left\{ {n \in \mathbb{N} \mid \sum\limits_{i = 1}^n {2i} \ne {n^2}} \right\}.$

Assume that $$C$$ is non-empty. Then, by the well ordering principle, there is a least element $$m \in C.$$ Obviously, $$P\left( m \right)$$ is false.

Given that $$P\left( 1 \right)$$ is true:

${LHS = \sum\limits_{i = 1}^1 {2i} = 2;\;\;}\kern0pt{ RHS = 1\left( {1 + 1} \right) = 2,}\;\; \Rightarrow {LHS = RHS,}$

we conclude that $$m \gt 1.$$ Hence, we can take the number $$m – 1,$$ for which the predicate $$P\left( {m – 1} \right)$$ is true. It is given by the expression

$\sum\limits_{i = 1}^{m – 1} {2i} = \left( {m – 1} \right)m.$

Add the next term $$2m$$ to both sides of the equation:

${\sum\limits_{i = 1}^m {2i} }={ \left( {m – 1} \right)m + 2m }={ {m^2} – m + 2m }={ {m^2} + m }={ m\left( {m + 1} \right).}$

We have obtained the true formula for the number $$m,$$ which contradicts our assumption. Consequently, the set of counterexamples $$C$$ is empty and the summation formula holds for all $$n \in \mathbb{N}.$$

### Example 3.

Show that $$n^5 – n$$ is divisible by $$5$$ for any $$n \in \mathbb{N}.$$

Solution.

Consider the predicate $$P\left( n \right)$$ that means that $$n^5 – n$$ is divisible by $$5$$ where $$n$$ is a natural number. It is easy to see that $$P\left( 1 \right)$$ is true, since $${1^5} – 1 = 0$$ is divisible by $$5.$$

By contradiction, suppose that $$P\left( n \right)$$ is false for certain $$n.$$ Let all such values of $$n$$ be represented by a set $$C:$$

${C = \left\{ {n \in \mathbb{N} \mid {n^5} – n}\right.}\kern0pt{\left.{\text{is not divisible by }5} \right\}.}$

The well ordering principle states that there is a least element $$m \in C$$ assuming $$C$$ is not an empty set. It follows from the above that $$m \gt 1$$ and hence, $$m -1$$ is also a natural number.

Thus, we have two facts: $$P\left( m \right)$$ is false, that is, $$m^5 -m$$ is not divisible by $$5,$$ but $$P\left( {m – 1} \right)$$ is true, so $${\left( {m – 1} \right)^5} – \left( {m – 1} \right)$$ is divisible by $$5.$$

We then have:

${{\left( {m – 1} \right)^5} – \left( {m – 1} \right) }={ {m^5} – 5{m^4} }+{ 10{m^3} – 10{m^2} + 5m – \cancel{1} – m + \cancel{1} }={ \left( {{m^5} – m} \right) }+{ \left( { – 5{m^4} + 10{m^3} – 10{m^2} + 5m} \right) }={ \left( {{m^5} – m} \right) }-{ 5m\left( {{m^3} – 2{m^2} + 2m – 1} \right).}$

In the last expression, the $$2\text{nd}$$ term $$5m\left( {{m^3} – 2{m^2} + 2m – 1} \right)$$ is divisible by $$5.$$ Hence, the $$1\text{st}$$ term $$\left( {{m^5} – m} \right)$$ is also divisible by $$5.$$ But this contradicts the statement that $$P\left( m \right)$$ is false!

So, our assumption (the set $$C$$ is not empty) is wrong, and consequently, $$P\left( n \right)$$ is true for all natural numbers.

### Example 4.

Show that $$4^n – 1$$ is divisible by $$3$$ for any $$n \in \mathbb{N}.$$

Solution.

We denote this divisibility property by $$P\left( n \right)$$ and prove it using well ordering. Notice that $$P\left( 1 \right)$$ is true since $${4^1} – 1 = 3$$ is divisible by $$3.$$

By contradiction, suppose that $$P\left( n \right)$$ is false for some $$n.$$ Let $$C$$ be the set that contains all such numbers $$n:$$

${C = \left\{ {n \in \mathbb{N} \mid {4^n – 1}}\right.}\kern0pt{\left.{\text{is not divisible by }3} \right\}.}$

If $$C$$ is not empty, then by the well ordering principle, it has a smallest element $$m \gt 1.$$ It is obvious that $$P\left( m \right)$$ is false.

From the other side, $$P\left( {m – 1} \right)$$ is true, that is, $${4^{m – 1}} – 1$$ is divisible by $$3.$$

After some algebra we get

${{4^m} – 1 = 4 \cdot {4^{m – 1}} – 1 }={ 4 \cdot {4^{m – 1}} – 4 + 3 }={ 4\left( {{4^{m – 1}} – 1} \right) + 3.}$

Here the first term $$4\left( {{4^{m – 1}} – 1} \right)$$ is divisible by $$3$$ by the previous assertion. Hence, the initial expression $${4^m} – 1$$ is also divisible by $$3.$$ This is a contradiction!

We conclude that set of counterexamples $$C$$ is empty and, hence, the property $$P\left( n \right)$$ holds for all $$n \in \mathbb{N}.$$

### Example 5.

Prove that for all natural numbers $\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{n}{{n + 1}}.$

Solution.

Let $$P\left( n \right)$$ be the summation formula for a number $$n.$$ Using well ordering proof techniques, we suppose by contradiction that $$P\left( n \right)$$ is false for certain numbers $$n.$$ Let all such values of $$n$$ be collected in a set $$C:$$

${C \text{ = }}\kern0pt{\left\{ {n \in \mathbb{N} \,\Biggm|\,\sum\limits_{i = 1}^n {\frac{1}{{i\left( {i + 1} \right)}}} \ne \frac{n}{{n + 1}}} \right\}.}$

It is easy to see that $$P\left( 1 \right)$$ is true:

${LHS = \sum\limits_{i = 1}^1 {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{1}{{1\left( {1 + 1} \right)}} = \frac{1}{2},\;\;}\kern0pt{RHS = \frac{1}{{1 + 1}} = \frac{1}{2},}\;\; \Rightarrow {LHS = RHS.}$

Assume that the set $$C$$ is not empty. Then, by the well ordering principle, there is a least element $$m \in C,$$ such that $$P\left( m \right)$$ is false. It follows from the above that $$m \gt 1.$$

From the other side, $$P\left( {m – 1} \right)$$ must be true since $$m – 1 \not\in C.$$

The summation formula for $$n = m – 1$$ is given by

$\sum\limits_{i = 1}^{m – 1} {\frac{1}{{i\left( {i + 1} \right)}}} = \frac{{m – 1}}{m}.$

Add the term $${\large{\frac{m}{{m + 1}}}\normalsize}$$ to both sides of the equation:

${\sum\limits_{i = 1}^m {\frac{1}{{i\left( {i + 1} \right)}}} }={ \frac{{m – 1}}{m} + \frac{1}{{m\left( {m + 1} \right)}} }={ \frac{{\left( {m – 1} \right)\left( {m + 1} \right) + 1}}{{m\left( {m + 1} \right)}} }={ \frac{{{m^2} – \cancel{1} + \cancel{1}}}{{m\left( {m + 1} \right)}} }={ \frac{{{m^2}}}{{m\left( {m + 1} \right)}} }={ \frac{m}{{m + 1}}.}$

This implication shows that if $$P\left( {m – 1} \right)$$ is true, then $$P\left( {m} \right)$$ is also true, which contradicts the assumption. Hence, the set of counterexamples $$C$$ is empty, and the given summation formula holds for all natural numbers.

### Example 6.

Prove by well ordering principle that $\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{{n + 1}}{{2n}}$ for $$n \ge 2.$$

Solution.

Let $$P\left( n \right)$$ be the product formula for a number $$n.$$ By contradiction, suppose that $$P\left( n \right)$$ is false for some $$n.$$ Let the set $$C$$ represent all such counterexamples:

${C \text{ = }}\kern0pt{\left\{ {n \in \mathbb{N} \,\Biggm|\,\prod\limits_{i = 2}^n {\left( {1 – \frac{1}{{{i^2}}}} \right)} \ne \frac{{n + 1}}{{2n}}} \right\}.}$

The property $$P\left( n \right)$$ is valid for $$n = 2:$$

${LHS = \prod\limits_{i = 2}^2 {\left( {1 – \frac{1}{{{i^2}}}} \right)} = 1 – \frac{1}{{{2^2}}} = \frac{3}{4},\;\;}\kern0pt{RHS = \frac{{2 + 1}}{{2 \cdot 2}} = \frac{3}{4},}\;\; \Rightarrow {LHS = RHS.}$

Suppose that $$C$$ is not empty. Then, by $$WOP,$$ it contains a least number $$m.$$ Since $$m \ge 2,$$ then $$m – 1$$ is also a natural number.

We have two facts: $$P\left( m \right)$$ is false and $$P\left( {m – 1} \right)$$ is true. Let’s show that there is the implication $$P\left( {m – 1} \right) \Rightarrow P\left( m \right).$$ For $$n = m – 1$$ we have:

$\prod\limits_{i = 2}^{m – 1} {\left( {1 – \frac{1}{{{i^2}}}} \right)} = \frac{m}{{2\left( {m – 1} \right)}}.$

Multiply both sides of this equation by $${\left( {1 – \large{\frac{1}{{{m^2}}}}\normalsize} \right)}.$$ This yields:

${\prod\limits_{i = 2}^m {\left( {1 – \frac{1}{{{i^2}}}} \right)} }={ \frac{m}{{2\left( {m – 1} \right)}} \cdot \left( {1 – \frac{1}{{{m^2}}}} \right) }={ \frac{m}{{2\left( {m – 1} \right)}} \cdot \frac{{{m^2} – 1}}{{{m^2}}} }={ \frac{{\cancel{m}\cancel{\left( {m – 1} \right)}\left( {m + 1} \right)}}{{2{m^{\cancel{2}}}\cancel{\left( {m – 1} \right)}}} }={ \frac{{m + 1}}{{2m}}.}$

Thus, the true assertion $$P\left( {m – 1} \right)$$ implies that $$P\left( {m} \right)$$ is also true. This is a contradiction! Hence, our assumption (the set of counterexamples $$C$$ is not empty) is wrong and the property $$P\left( {n} \right)$$ holds for all $$n \ge 2.$$