Recitation 5 Theorem. For all n∈N:1+2+3+…+n=+ Proof. By contradiction. Assume that the theorem is false. Then, some natural numbers serve as counterexamples to it. Let's collect them in a set {n∈N|1+2+3+ +n By our assumption that the theorem admits counterexamples, C is a non-empty set of natural numbers. So, by the well-ordering principle, C has a minimum element, call it c That is, c is the smallest counterexample to the theorem Since c is a counterexample(cE C), we know that 1+2+3+…+c≠当 Since c is the smallest counterexample(c minimum of C), we know the theorem holds for all natural numbers smaller than c. (Otherwise at least one of them would also be in C and would therefore prevent c from being the minimum of C)[*] In particular, the theorem is true for c-1. That is 1+2+3+…+(c-1)= But then, adding c to both sides we get 1+2+3+…+(c-1)+c=2+c== hich means the theorem does hold for c, after all! That is, c is not a counterexample. But this is a contradiction And we are done Well, almost. Our argument contains a bug. Everything we said after [*] bases on the fact that c-l actually exists. That is, that there is indeed some natural number smaller than C. How do we know that? How do we know that c is not 0? Fortunately, this can be fixed. We know cf0 because c is a counterexample whereas 0 is not, as0=0(0+ 1)/2� � � � � Recitation 5 2 Theorem. For all n ∈ N: 1 + 2 + 3 + · · · + n = n(n 2 +1) . Proof. By contradiction. Assume that the theorem is false. Then, some natural numbers serve as counterexamples to it. Let’s collect them in a set: C = n ∈ N | 1 + 2 + 3 + · · · + n = n(n 2 +1) . By our assumption that the theorem admits counterexamples, C is a non­empty set of natural numbers. So, by the well­ordering principle, C has a minimum element, call it c. That is, c is the smallest counterexample to the theorem. Since c is a counterexample (c ∈ C), we know that 1 + 2 + 3 + · · · + c = c(c+1) . 2 Since c is the smallest counterexample (c minimum of C), we know the theorem holds for all natural numbers smaller than c. (Otherwise, at least one of them would also be in C and would therefore prevent c from being the minimum of C.) [∗] In particular, the theorem is true for c − 1. That is, 1 + 2 + 3 + · · · + (c − 1) = (c−1)c . 2 But then, adding c to both sides we get 2 = c −c+2c c(c+1) 1 + 2 + 3 + · · · + (c − 1) + c = , (c−1)c + c = 2 2 2 which means the theorem does hold for c, after all! That is, c is not a counterexample. But this is a contradiction. And we are done. Well, almost. Our argument contains a bug. Everything we said after [∗] bases on the fact that c − 1 actually exists. That is, that there is indeed some natural number smaller than c. How do we know that? How do we know that c is not 0? Fortunately, this can be fixed. We know c = 0 because c is a counterexample whereas 0 is not, as 0 = 0(0 + 1)/2