Recitation 3 3 Problem: A False Proof In lecture, we proved that: 1+2+3+...+m But now were going to prove a contradictory theorem False Theorem 1. For all n >0 n(2+ 2+3+4 P induction. Let P(n)be the pi ion that2+3+4+…+n=n(n+1)/ Base case: P(O)is true, since both sides of the equation are equal to zero. (Recall that a sum with no terms is zero. Inductive step: N P(n) implies P(n+1) suppos that P(n)is true; that is, 2+3+4+..+n=n(n+1)/2. Then we can reason as follows 2+3+4+…+n+(n+1)=[2+3+4+…+n]+(n+1) n(n+1) +(n+1) (n+1)(n+2) Above, we group some terms, use the assumption P(n), and then simplify. This shows that P(n) implies P(n+1). By the principle of induction, P(n) is true for all nEN. D kactly is the error in this proof? Solution. The short answer is that we failed to prove P(0)= P(), just as in the colored horses problem in lecture. In fact, once again, the error is rooted in the misleading nature of the ". notation More precisely, in the inductive step we are required to prove that P(n)implies P(n+1) for all n >0. However, the argument given above breaks down when n =0. Let's look more closely at the first equation in the indutive step to see why 2+3+4+…+n+(n+1)=[2+3+4+…+n]+(m+1) This seems completely ous; after all, weve only grouped terms! However, the left side contains no terms when n =0. The"... is compeletely misleading in this case; 2, 3, 4, and n+l are actually not in the sum. This misimpression becomes an error when we"pull out"the(n+ 1) term on the right side, disregarding the fact that no such term actually existed on the left. Thus, for n=0, the equation weve just written down says 2+3+4+…+n+(n+1)=2+3+4+� � � � � � Recitation 3 4 3 Problem: A False Proof In lecture, we proved that: n(n + 1) 1 + 2 + 3 + . . . + n = 2 But now we’re going to prove a contradictory theorem! False Theorem 1. For all n ≥ 0, n(n + 1) 2 + 3 + 4 + . . . + n = 2 Proof. We use induction. Let P(n) be the proposition that 2 + 3 + 4 + . . . + n = n(n + 1)/2. Base case: P(0) is true, since both sides of the equation are equal to zero. (Recall that a sum with no terms is zero.) Inductive step: Now we must show that P(n) implies P(n + 1) for all n ≥ 0. So suppose that P(n) is true; that is, 2 + 3 + 4 + . . . + n = n(n + 1)/2. Then we can reason as follows: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + . . . + n + (n + 1) n(n + 1) = + (n + 1) 2 (n + 1)(n + 2) = 2 Above, we group some terms, use the assumption P(n), and then simplify. This shows that P(n) implies P(n + 1). By the principle of induction, P(n) is true for all n ∈ N. Where exactly is the error in this proof? Solution. The short answer is that we failed to prove P(0) ⇒ P(1), just as in the colored horses problem in lecture. In fact, once again, the error is rooted in the misleading nature of the “. . .” notation. More precisely, in the inductive step we are required to prove that P(n) implies P(n+1) for all n ≥ 0. However, the argument given above breaks down when n = 0. Let’s look more closely at the first equation in the indutive step to see why: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + . . . + n + (n + 1) This seems completely innucuous; after all, we’ve only grouped terms! However, the left side contains no terms when n = 0. The “. . .” is compeletely misleading in this case; 2, 3, 4, and n + 1 are actually not in the sum. This misimpression becomes an error when we “pull out” the (n + 1) term on the right side, disregarding the fact that no such term actually existed on the left. Thus, for n = 0, the equation we’ve just written down says: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + � . . . + n + (n + 1) � �� � �� � � �� � =0 =0 =1