Induction ill 4 Common induction mistakes There are several potholes that students commonly fall into while trying to write induc tion proofs. Some are simple, some are quite subtle. Collectively, these traps cost 6.042 students thousands of points every term. Here are the top grade -gutters and how to avoid them.(Alternatively, if you mash all these blunders into a single proof, you might be able to drive your ta bananas. 4.1 The Misplaced Quantifier Let's start with a simple, relatively minor gotcha. Can you spot the problem? Theorem 5. For alln >0 n(2n+1)(n+1) 6 Proof. We use induction. Let P(n)be the proposition, "For all n >0, 12+22+..+n2 In general, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. The goal of an induction proof is to prove that P(n)=“12+2+…+n2 2n+1)(n+1 In the erroneous proof above, the predicate P(n)itself asserts that an equation holds for all 20. This makes no sense. The"For all n >0"bit should not be part of the induction hypothes 4.2 Misusing a Predicate as a Numerical function Here's another classic. This one is a pretty major error. Theorem 6. For all n >0 n(2n+1)(7+1)8 Induction III 4 Common Induction Mistakes There are several potholes that students commonly fall into while trying to write induc￾tion proofs. Some are simple, some are quite subtle. Collectively, these traps cost 6.042 students thousands of points every term. Here are the top grade­gutters and how to avoid them. (Alternatively, if you mash all these blunders into a single proof, you might be able to drive your TA bananas.) 4.1 The Misplaced Quantifier Let’s start with a simple, relatively minor gotcha. Can you spot the problem? Theorem 5. For all n ≥ 0: 2 12 + 22 + . . . + n = n(2n + 1)(n + 1) 6 2 Proof. We use induction. Let P(n) be the proposition, “For all n ≥ 0, 12 + 22 + . . . + n = n(2n + 1)(n + 1)/6”. Base case. Etc. × In general, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. The goal of an induction proof is to prove that P(n) is true for all n ≥ 0. A valid induction hypothesis in this case would be: 2 P(n) = “12 + 22 + . . . + n = n(2n + 1)(n + 1) ” 6 In the erroneous proof above, the predicate P(n) itself asserts that an equation holds for all n ≥ 0. This makes no sense. The “For all n ≥ 0” bit should not be part of the induction hypothesis. 4.2 Misusing a Predicate as a Numerical Function Here’s another classic. This one is a pretty major error. Theorem 6. For all n ≥ 0: 2 12 + 22 + . . . + n = n(2n + 1)(n + 1) 6