Well Ordering Principle for a sum and why we only care about the set less than the smallest in our counter example set?

Question

I was trying to prove:

$$ \sum_{i=1}^n{i} = \frac{n(n+1)}{2}$$

using the WOP.

I think the part that is confusing me about this proof is a more general pattern for proofs by WOP.

To prove it we say that there exists a set of counter examples:

$$C = \{ n \in \mathbb{N} \mid \sum_{i=1}^n{i} \neq \frac{n(n+1)}{2} \} $$

So we know the claim is false for the the smallest element, say c, $n = c$ but the claim is true for $n<c$. My question is very simple. Why do we focus on the truth that it holds for $n<c$ but neglect/ignore other elements that might make the sum true? i.e. why do we not state instead that the sum (i.e. $\sum_{i=1}^n{i} = \frac{n(n+1)}{2}$) is True for:

$$T = \{ (n<c) \cup n \notin C\}$$

i.e. include not only $n < c$?

Does that omission affect the proof or is stating only the set $n<c$ a way to restrict our attention to the set that matters to reach the contradiction?

Answer 1

Let me begin by saying that we do not assume that the statement is true for all values $n$ such that $c < n$. I think you may have misspoken in writing that.

Your last sentence is correct. We assume that the statement is true for all $n < c$, and we are required to deduce from this that it is also true for $c$, whence a contradiction.

The reason we don't talk about the other values $n > c$ for which the statement is true, is that we know little about them. Our only assumption is that $c$ is the smallest value for which the statement is false. This does allow us to conclude that the statement is true for values $n < c$, but usually allows us to say nothing about values $n > c$.

In specific instances, it may be possible to deduce something about values $n > c$ from the assumption that $c$ is the smallest number for which the statement is false, and any method of deriving a contradiction will do the job. But this is not the case in general.

Answer 2

This is basically the contrapositive of induction. You assume the set of cases where the formula fails has a smallest element, $c$. That tells you that the formula works for all smaller values, in particular for $c-1$ So if the formula is true for $c-1$ you derive the fact that it is true for $c$, contradicting the assumption. Note that you have to prove the formula for a base case, or it could be false for all $n$. So your proof would be:
True for $n=1$ because $\sum_{i=1}^1 i =1 = \frac {1(1+1)}2$
Assume the first failure is $c$, then the formula is true for $c-1$ so
$\sum_{i=1}^{c-1} i =\frac {c(c-1)}2$
Now add $c$ to both sides and show the new formula is satisfied, so $c$ is not a failure.

Answer 3

What you want to do is prove that $C$ is actually equal to the empty set.

You start by assuming that $C$ is not the empty set.

At this point, we have no idea which numbers are in $C$ and which are not. We may discover, for example, that $10 \not \in C$. But that tells us nothing about whether or not $5 \in C$ or $50 \in C$.

Then it must have a smallest element, say $c \in C$.

So, what does that tell us? Let's say that $c = 5$. Then we still don't know if $50 \in C$ is true or not, but we now know, within the limits of our assumption, that $4 \not \in C$.

Since $\sum_{i=1}^1{i} = 1 = \frac{1(1+1)}{2}$, we know that $c \ne 1$.

The important thing about the number $1$ is that it is the smallest member of $\mathbb N$. So, since $c \ne 1$, then $c-1$ is also a member of $\mathbb N$. So $c-1 \in \mathbb N$ and $c-1 < c$. Since $c$ is the smallest member of $C$, then $c-1 \not \in C$.

So $c-1 \in \mathbb N$ but $c-1 \not \in C$.

Now we are ready to create a contradiction. We will show that $c-1 \not \in C$ implies $c \not \in C$.

But $c-1 \not \in C$ implies $\sum_{i=1}^{c-1}{i} = \frac{(c-1)(c-1+1)}{2}$ implies $\sum_{i=1}^{c}{i} = \frac{(c)(c+1)}{2}$.

But then, $c \not \in C$. Which is a contradiction.

So our assumption that $C$ is not equal to the empty set must be false.

So, in fact, $C = \varnothing$.

In other words, $\sum_{i=1}^{n}{i} = \frac{(n)(n+1)}{2}$ is true for all $n \in \mathbb N$.