2.2: Template for Well Ordering Proofs

More generally, there is a standard way to use Well Ordering to prove that some property, \(P(n)\) holds for every nonnegative integer, \(n\). Here is a standard way to organize such a well ordering proof:

To prove that “\(P(n)\) is true for all \(n \in \mathbb{N}\)” using the Well Ordering Principle:

• Define the set, \(C\), of counterexamples to \(P\) being true. Specifically, define

\[\nonumber C ::= \{n \in \mathbb{N} \mid \text{NOT}(P(n)) \text{ is true}\}. \]

The notation \( \{n \mid Q(n)\}\) means “the set of all elements \(n\) for which \(Q(n)\) is true.” See Section 4.1.4.

• Assume for proof by contradiction that \(C\) is nonempty.
• By the Well Ordering Principle, there will be a smallest element, \(n\), in \(C\).
• Reach a contradiction somehow—often by showing that \(P(n)\) is actually true or by showing that there is another member of \(C\) that is smaller than \(n\). This is the open-ended part of the proof task.
• Conclude that \(C\) must be empty, that is, no counterexamples exist. \(\quad \blacksquare\)

Summing the Integers

Let’s use this template to prove

Theorem \(\PageIndex{1}\)

\[\label{2.2.1} 1 + 2 + 3 + \cdots + n = n(n + 1)/2\]

for all nonnegative integers, \(n\).

First, we’d better address a couple of ambiguous special cases before they trip us up:

• If \(n = 1\), then there is only one term in the summation, and so \(1 + 2 + 3 + \cdots + n\) is just the term 1. Don’t be misled by the appearance of 2 and 3 or by the suggestion that 1 and n are distinct terms!
• If \(n = 0\), then there are no terms at all in the summation. By convention, the sum in this case is 0.

So, while the three dots notation, which is called an ellipsis, is convenient, you have to watch out for these special cases where the notation is misleading. In fact, whenever you see an ellipsis, you should be on the lookout to be sure you understand the pattern, watching out for the beginning and the end.

We could have eliminated the need for guessing by rewriting the left side of (\ref{2.2.1}) with summation notation:

\[\nonumber \sum_{i = 1}^{n} i \quad \text{or} \quad \sum_{1 \leq i \leq n} i .\]

Both of these expressions denote the sum of all values taken by the expression to the right of the sigma as the variable, \(i\), ranges from 1 to \(n\). Both expressions make it clear what (\ref{2.2.1}) means when \(n = 1\). The second expression makes it clear that when \(n = 0\), there are no terms in the sum, though you still have to know the convention that a sum of no numbers equals 0 (the product of no numbers is 1, by the way).

OK, back to the proof:

Proof. By contradiction. Assume that Theorem 2.2.1 is false. Then, some nonnegative integers serve as counterexamples to it. Let’s collect them in a set:

\[\nonumber C ::= \{n \in \mathbb{N} \mid 1 + 2 + 3 + \cdots + n \neq \frac{n(n+1)}{2}\}. \]

Assuming there are counterexamples, \(C\) is a nonempty set of nonnegative integers. So, by the Well Ordering Principle, \(C\) has a minimum element, which we’ll call \(c\). That is, among the nonnegative integers, \(c\) is the smallest counterexample to equation (\ref{2.2.1}).

Since \(c\) is the smallest counterexample, we know that (\ref{2.2.1}) is false for \(n = c\) but true for all nonnegative integers \(n < c\). But (\ref{2.2.1}) is true for \(n = 0\), so \(c > 0\). This means \(c = 1\) is a nonnegative integer, and since it is less than \(c\), equation (\ref{2.2.1}) is true for \(c - 1\). That is,

\[\nonumber 1 + 2 + 3 + \cdots + (c - 1) = \frac{(c-1)c}{2}. \]

But then, adding \(c\) to both sides, we get

\[\nonumber 1 + 2 + 3 + \cdots + (c - 1) = \frac{(c-1)c}{2} + c = \frac{c^2 - c + 2c}{2} = \frac{c(c+1)}{2}. \]

which means that (\ref{2.2.1}) does hold for \(c\), after all! This is a contradiction, and we are done. \(\quad \blacksquare\)