Calculus

Set Theory

Set Theory Logo

Well Ordering Principle

Solved Problems

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;\;\;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;\;\; 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 \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}\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 = \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},\;\;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 \({\frac{m}{{m + 1}}}\) 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 = \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},\;\;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 - \frac{1}{{{m^2}}}} \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.\)

Page 1 Page 2