Recitation 5 2 Problem: Well-ordering principle Here is the geometric sum formula, which you proved in a previous recitation Use the well-ordering principle to prove that, when+ l, the formula is true for alln E N Prepare a complete, careful solution! Proof. By contradiction. Suppose the theorem is not true on all natural numbers, but instead it admits some counterexamples. Let C be the set of these counterexamples C={n∈N|1+r+2+…+r≠} By our assumption, C is a non-empty set of natural numbers. So, the well-ordering prin ciple guarantees C has a minimum element c. So, c is the smallest counterexample to the eorem Because c is a counterexample we know 1+7+n2+…+r≠ Because 1=(1-r)/(1-r), we know 0 is not a counterexample, and therefore c>0 Because c is the smallest counterexample, we know all numbers smaller than c satisfy the theorem -and such numbers do exist, as c>0. In particular c- l satisfies the theorem But then, adding r" to both sides of the equation, we get 1+r+r2+…+r-1+r°=+r°=11-r°+°-r+]=与 which implies c is not really a counterexample, a contradiction. Therefore there cant be any counterexamples to the theorem the theorem is true. D� � � Recitation 5 3 2 Problem: Well­ordering principle Here is the geometric sum formula, which you proved in a previous recitation. 3 1 + r + r 2 + r + . . . + r n = 1 − rn+1 1 − r Use the well­ordering principle to prove that, when r = 1, the formula is true for all n ∈ N. Prepare a complete, careful solution! Solution. Proof. By contradiction. Suppose the theorem is not true on all natural numbers, but instead it admits some counterexamples. Let C be the set of these counterexamples: | � 1− 1 r − n r +1 C = n ∈ N 1 + r + r 2 + · · · + r n = . By our assumption, C is a non­empty set of natural numbers. So, the well­ordering prin￾ciple guarantees C has a minimum element c. So, c is the smallest counterexample to the theorem. Because c is a counterexample, we know 1−rc+1 1 + r + r 2 + · · · + r c =� . 1−r Because 1 = (1 − r1)/(1 − r), we know 0 is not a counterexample, and therefore c > 0. Because c is the smallest counterexample, we know all numbers smaller than c satisfy the theorem —and such numbers do exist, as c > 0. In particular, c − 1 satisfies the theorem 1−rc 1 + r + r 2 + · · · + r c−1 = 1−r . But then, adding rc to both sides of the equation, we get 1−rc c 1−rc+1 c 1 1 + r + r 2 + · · · + r c−1 + r = 1−r + r c = 1−r [1 − r c + r − r c+1] = 1−r which implies c is not really a counterexample, a contradiction. Therefore, there can’t be any counterexamples to the theorem. The theorem is true