Below we present three proofs by contradiction that utilize the Well-Ordering Principle. These proofs may be correct or they may have an error. For each proof identify if it is correct, or select the choice which best describes the error if it has one.

Theorem: Vx E N. ) 2 = 2 = 2n+1 - 1. i=0 Proof: We proceed by contradiction. n Suppose The statement is false, that is assume In ( N. ) 2" # 2" - 1. In this case, we'll let C be the set of all values of 7 which make that statement true, i.e. C' = {n ) 2' * 2" ) - 1}. Since we assumed that i=0 i=0 there is at least one value of n such that > 2 2" - 1, it must be that C is not empty. By applying the Well-Ordering Principle, it must be that C has a smallest element, we'll call that y. i=0 By our definition of y, we have that ) 2' * 23+ - 1. This means that ) 21 - 23 23+1 - 1 - 2". Note that ) 2' - 2y , so 21 # 23+1 - 1 - 2". Also, observe that i=0 1=0 i=0 i=0 y-1 23+1 - 1 - 29 = 23+1 - 23 - 1 = 23 .2 - 2" -1 = 2"(2 -1) - 1 = 2" - 1. Therefore we have that 2' # 2" - 1 and so it must be that (y - 1) E C. This contradicts that y was the smallest element of C. 1= 0 Since our assumption that ( was non-empty produced a contradiction, it must be that C was empty, and so we can conclude Vac EN. ) (2) = 2"+1 - 1. i=0 A. O This proof is correct. B. O This proof incorrectly negates the theorem. C. O This proof incorrectly uses the Well-Ordering Principle. D. O This proof made an algebra error. E. O This proof did not arrive at a contradiction