So the problem is that:
Use the Well Ordering Principle (WOP) to prove that
$2+4+···+2n = n(n+1)$
for all $n > 0$.
1.My first thought is that we can create a set named $C::=\{n>0\mid2+4+···+2n ≠ n(n+1)\}$. This set is not empty and all its elements are non-negative integers. So according to the well ordering principle we can conclude that this set has a minimum number called $k$.
2.So we have $\color{red}{2+4+···+2k ≠ k(k+1)}$ (marked as a). While $k/2$ is smaller than $k$, we can also conclude that $2+4+···+2(k/2) = (k/2)(k/2+1)$. Therefore,we can conclude that $\color{red}{2+4+···+2(k/2)+2k = (k/2)(k/2+1) + 2k}$ (marked as b).
3.Now the problem should change to prove the right side of the expression b equals to the right side of the expression a,that is to say, we should prove that $k(k+1)=(k/2)(k/2+1) + 2k$, so here the conflict happen and we can say that the presume is false.Therefore,the original proposition should be true.
The problem is :How should I prove that $k(k+1)=(k/2)(k/2+1) + 2k$? It seems that I can never prove this.So maybe I thought wrongly at first.But how can I solve this problem?
Best Answer
What you will demonstrate in this exercise is that there is a very natural equivalence between well-ordering and induction.
You did a good job by defining $C$. But, in fact, $C$ is empty, which is what you need to prove. So, by means of contradiction, you need to assume that it is not. Then, as you suggest, it has a minimal member $k$. Now, you have to split into two cases: either $k=1$ or $k-1$ is a positive integer that is not in $C$ The first case would be the base case of an induction proof, and the second is essentially the induction hypothesis that will lead to a contradiction when you conclude that $k\notin C$ by doing the algebra.