Problem 3. Consider the following induction proof: Inductive Statement: P(n) = If a, b N...

 

Transcribed Image Text:

Problem 3. Consider the following induction "proof": Inductive Statement: P(n) = "If a, b € N with max(a, b) = n, then a = = b." Base Step: For n = 0, suppose that a, b E N with max(a, b) a ≥ 0. Moreover, a ≤ max(a, b) = = b. a = = 0. Since a is a natural number, 0. Thus, a = 0. The same reasoning shows that b = 0, so Inductive Step: As our inductive hypothesis, we assume that P(k) is true for some k € N. That is, if a, b E N with max(a, b) = k, then a = b. Now, we consider P(k + 1). Suppose that a', b' E N with max(a', b') k1. Then, max(a' 1, b' - 1) = k. Letting a = a' - 1 and b = b' - 1, we can appeal to the inductive hypothesis to conclude that a' – 1= a = b = b' - 1, so a' = b'. We have shown that P(k + 1) is true under the assumption that P(k) is. - By induction, we have shown that P(n) is true for all n € N. Letting a = 4 and b = Explain the mistake that was made. = 8 shows that P(8) is false, so something has gone wrong in the proof. Problem 3. Consider the following induction "proof": Inductive Statement: P(n) = "If a, b € N with max(a, b) = n, then a = = b." Base Step: For n = 0, suppose that a, b E N with max(a, b) a ≥ 0. Moreover, a ≤ max(a, b) = = b. a = = 0. Since a is a natural number, 0. Thus, a = 0. The same reasoning shows that b = 0, so Inductive Step: As our inductive hypothesis, we assume that P(k) is true for some k € N. That is, if a, b E N with max(a, b) = k, then a = b. Now, we consider P(k + 1). Suppose that a', b' E N with max(a', b') k1. Then, max(a' 1, b' - 1) = k. Letting a = a' - 1 and b = b' - 1, we can appeal to the inductive hypothesis to conclude that a' – 1= a = b = b' - 1, so a' = b'. We have shown that P(k + 1) is true under the assumption that P(k) is. - By induction, we have shown that P(n) is true for all n € N. Letting a = 4 and b = Explain the mistake that was made. = 8 shows that P(8) is false, so something has gone wrong in the proof.

Answer rating: 100% (QA)

The mistake that was made was in the inductive step We assumed that Pk 1 was true ... View the full answer