Inductive step: Assume that P(n)is true, where n is any natural number. Then 3|(m3-n)→3|(n3-n)+3(n2+n) →3|n23+3n2+3n+1-n-1 →3|(n+1)3-(n+1) The first implication relies on the fact that 3(n=+ n) is divisible by 3. The remaining implications involve only rewriting the expression on the right. The last statement is P(n+1), so weve proved that P(n)implies P(n+ 1)for all nE N By the principle of induction, P(n) is true for all n E N, which proves the clair This proof would look quite mysterious to anyone not privy to the scratchwork we did beforehand. In particular, one might ask how we had the foresight to introduce the magi term 3(n2+n). Of course, this was not foresight at all; we just worked backward initially! 4 A Faulty Induction Proof Sometimes we want to prove that a statement is true for, say, all integers n 1 rather than all integers n>0. In this circumstance we can use a slight variation on induction prove P(1) in the base case and then prove that P(n)implies P(n+1) for all n 1 in the inductive step. This is a perfectly valid variant of induction and is not the problem with the proof below False Theorem 3. All horses are the same color Proof. The proof is by induction. Let P(n) be the proposition that in every set of n horses, ll are the same color Base case: P(1)is true because all horses in a set of 1 must be the same color Inductive step: Assume that P(n)is true, where n is a positive integer; that is, assume that in every set of n horses, all are the same color. Now consider a set of n+l horses h1, h By our assumption the first n horses are the same color me color also by our assumption the last n horses are the same color� �� � � �� � 6 Induction I Inductive step: Assume that P(n) is true, where n is any natural number. Then: 2 3 (n 3 − n) ⇒ 3 (n 3 | | − n) + 3(n + n) ⇒ 3 n 3 + 3n 2 | + 3n + 1 − n − 1 ⇒ 3 (n + 1)3 | − (n + 1) The first implication relies on the fact that 3(n2 + n) is divisible by 3. The remaining implications involve only rewriting the expression on the right. The last statement is P(n + 1), so we’ve proved that P(n) implies P(n + 1) for all n ∈ N. By the principle of induction, P(n) is true for all n ∈ N, which proves the claim. This proof would look quite mysterious to anyone not privy to the scratchwork we did beforehand. In particular, one might ask how we had the foresight to introduce the magic term 3(n2 + n). Of course, this was not foresight at all; we just worked backward initially! 4 A Faulty Induction Proof Sometimes we want to prove that a statement is true for, say, all integers n ≥ 1 rather than all integers n ≥ 0. In this circumstance, we can use a slight variation on induction: prove P(1) in the base case and then prove that P(n) implies P(n + 1) for all n ≥ 1 in the inductive step. This is a perfectly valid variant of induction and is not the problem with the proof below. False Theorem 3. All horses are the same color. Proof. The proof is by induction. Let P(n) be the proposition that in every set of n horses, all are the same color. Base case: P(1) is true, because all horses in a set of 1 must be the same color. Inductive step: Assume that P(n) is true, where n is a positive integer; that is, assume that in every set of n horses, all are the same color. Now consider a set of n + 1 horses: h1, h2, . . . , hn, hn+1 By our assumption, the first n horses are the same color: h1, h2, . . . , hn, hn+1 same color Also by our assumption, the last n horses are the same color: h1, h2, . . . , hn, hn+1 same color