Mathematical Induction - Study Guide

Problem: For each positive integer n, the formula 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = n(n + 1)(2n + 7) 6 is valid. Proof: (formal style; it is good to do a few proofs this way) We will use the Principle of Mathematical Induction. Let S be the set of all positive integers n such that 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = n(n + 1)(2n + 7) . 6 Since 1 · 3 = (1 · 2 · 9)/6, it is clear that 1 ∈ S. Suppose that k ∈ S for some positive integer k. We then have 1 · 3 + 2 · 4 + 3 · 5 + · · · + (k + 1)(k + 3) = 1 · 3 + 2 · 4 + 3 · 5 + · · · + k(k + 2) + (k + 1)(k + 3) k(k + 1)(2k + 7) + (k + 1)(k + 3) 6 ¢ k+1¡ 2 = 2k + 7k + 6k + 18 6 k+1 = (k + 2)(2k + 9) 6 ¡ ¢ (k + 1)(k + 2) 2(k + 1) + 7 = . 6 (substituting k + 1 for n) (include extra term) = (since k ∈ S) (factoring) (more factoring) (the form we want) This shows that k + 1 ∈ S. By the Principle of Mathematical Induction, it follows that S = Z + . Hence, 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = n(n + 1)(2n + 7) 6 for all positive integers n. Proof: (informal style; more common in textbooks) The formula given in the statement of the problem is clearly true for n = 1. Suppose that the formula is valid for some positive integer k. Then k(k + 1)(2k + 7) + (k + 1)(k + 3) 6 ¢ k+1¡ 2 2k + 7k + 6k + 18 = 6 ¡ ¢ (k + 1)(k + 2) 2k + 9 , = 6 1 · 3 + 2 · 4 + 3 · 5 + · · · + (k + 1)(k + 3) = showing that the formula is valid for k + 1 as well. The result now follows by the Principle of Mathematical Induction. Here are three PMI proofs of this same result, each with one or more errors; be certain you can spot the errors. Proof: We will use the Principle of Mathematical Induction. Since 1 · 3 = (1 · 2 · 9)/6, it is clear that the formula works when n = 1. Suppose that k ∈ S for some positive integer k. We then have k(k + 1)(2k + 7) + (k + 1)(k + 3) 6 ¢ k+1¡ 2 = 2k + 7k + 6k + 18 6 (k + 1)(k + 2)(2k + 9) = , 6 1 · 3 + 2 · 4 + 3 · 5 + · · · + (k + 1)(k + 3) = so k + 1 ∈ S. By the Principle of Mathematical Induction, 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = n(n + 1)(2n + 7) 6 for all positive integers n. Proof: We will use the Principle of Mathematical Induction. Since 1 · 3 = (1 · 2 · 9)/6, it is clear that the formula works when n = 1. Now suppose that the formula is valid for every positive integer k. Then k(k + 1)(2k + 7) + (k + 1)(k + 3) 6 ¢ k+1¡ 2 = 2k + 7k + 6k + 18 6 ¡ ¢ (k + 1)(k + 2) 2(k + 1) + 7 = , 6 1 · 3 + 2 · 4 + 3 · 5 + · · · + (k + 1)(k + 3) = so the formula works for all n. Proof: We will use the Principle of Mathematical Induction. Let S be the set of all positive integers n such that n(n + 1)(2n + 7) . 6 Since 1 · 3 = (1 · 2 · 9)/6, it is clear that 1 ∈ S. Suppose that k ∈ S for some positive integer k. We then have 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = ¡ ¢ (k + 1)(k + 2) 2(k + 1) + 7 1 · 3 + 2 · 4 + 3 · 5 + · · · + (k + 1)(k + 3) = 6 (k + 1)(k + 2)(2k + 9) k(k + 1)(2k + 7) + (k + 1)(k + 3) = 6 6 ¡ ¢ k+1 k+1 (2k 2 + 13k + 18). 2k 2 + 7k + 6k + 18 = 6 6 This shows that k + 1 ∈ S. By the Principle of Mathematical Induction, it follows that S ∈ Z + . Hence, 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = for all positive integers n. n(n + 1)(2n + 7) 6 Here are three correct proofs for a different result; study them carefully. Theorem: For each positive integer n, the integer 32n+1 + 2n+2 is divisible by 7. Proof 1: We will use the Principle of Mathematical Induction. Let S be the set of all positive integers n for which 32n+1 + 2n+2 is divisible by 7. When n = 1, we see that 33 + 23 = 35 is divisible by 7. This shows that 1 ∈ S. Now suppose that k ∈ S for some positive integer k. Since 32k+1 + 2k+2 is divisible by 7, there exists an integer q such that 32k+1 + 2k+2 = 7q. We then have (using one of several options) 32k+3 + 2k+3 = 32 · 32k+1 + 2 · 2k+2 ¢ ¡ = 7 · 32k+1 + 2 32k+1 + 2k+2 = 7 · 32k+1 + 2(7q) ¡ ¢ = 7 32k+1 + 2q , revealing that 7 divides 32k+3 + 2k+3 . This means that k + 1 ∈ S. By the Principle of Mathematical Induction, S = Z+ . Hence, the integer 32n+1 + 2n+2 is divisible by 7 for each positive integer n. Proof 2: We will use the Principle of Mathematical Induction. For each positive integer n, let Pn be the statement that 32n+1 + 2n+2 is divisible by 7. Since 33 + 23 = 35 is divisible by 7, it is clear that P1 is true. Suppose that Pk is true for some positive integer k. Since 32k+1 + 2k+2 is divisible by 7, there exists an integer q such that 32k+1 + 2k+2 = 7q. We then have (using one of several options) 32k+3 + 2k+3 = 32 · 32k+1 + 2 · 2k+2 ¡ ¢ = 9 7q − 2k+2 + 2 · 2k+2 = 63q − 7 · 2k+2 ¡ ¢ = 7 9q − 2k+2 , revealing that 7 divides 32k+3 + 2k+3 . This means that Pk+1 is true. By the Principle of Mathematical Induction, all of the Pn statements are true, that is, the integer 32n+1 + 2n+2 is divisible by 7 for each positive integer n. Proof 3: The statement is easily seen to be true when n = 1. Suppose that 32k+1 + 2k+2 is divisible by 7 for some positive integer k and choose an integer q such that 32k+1 + 2k+2 = 7q. We then have 32k+3 + 2k+3 = 32 · 32k+1 + 2 · 2k+2 ¡ ¢ = 9 32k+1 + 2k+2 − 7 · 2k+2 ¡ ¢ = 9 7q − 7 · 2k+2 ¡ ¢ = 7 9q − 2k+2 , revealing that 7 divides 32k+3 + 2k+3 . By the Principle of Mathematical Induction, the integer 32n+1 + 2n+2 is divisible by 7 for each positive integer n.