1 CmSc 175 Discrete Mathematics Lesson 09: Mathematical Induction 1. Introduction This is a proof method, used to prove properties of objects that exhibit certain regularities. Example: Consider the sum of the first k odd integers: k sum of k odd integers equal to: 1 1 1 2 1 + 3 4 3 1 + 3 + 5 9 4 1 + 3 + 5 + 7 16 …. k 1 + 3 + …+ 2k-1 k2 We can guess that the sum is k2 But how do we prove it? We can prove it using mathematical induction. Mathematical induction is applicable to objects that have some regularities and can be ordered. Regularities and ordering are discussed below. 2. The principle of mathematical induction We want to prove a property, and we denote this property by a predicate P(n), defined for all integers n. Let a be some fixed integer Suppose that the following two statements are true: 1. P(a) is true 2. For all integers k  a, if P(k) is true then P(k+1) is true Then the statement For all integers n  a, P(n) is also true. Note: in most cases a = 1.2 3. Proof by mathematical induction Preparation: Order the elements for which a property is to be proved. a1, a2, …. an, …. Determine what relation exists between ak+1 and ak Proof steps: 1. Inductive base: Show the property P for the first element a1, i.e. show that P(1) is true. 2. Inductive step: Show that the conditional P(k)  P(k+1) is true, i.e. if the property is true for the k-th element, then it is true for the (k+1)-st element How to do step 1: directly (see examples below) How to do step 2: We know that the conditional P  Q is true in all cases except for one: when P is true but Q is false. This is the case we need to consider and to show that when P(k) is true, P(k+1) is also true. 1. Assume that P(k) is true 2. Show that P(k+1) is true, using the regularity - the relation between ak+1 and ak Then, by the principle of mathematical induction it will follow that the property is true for all objects. Example 1: Consider the sequence 1, 2, 4, 8, 16, ….. a0 = 1, an+1 = 2 * an, n = 0,1, 2, 3, …. Prove by mathematical induction that an = 2n Proof: The predicate to consider is P(n) : an = 2n3 1. Inductive base: Show that P(0) is true. Substitute n = 0 in the expression an = 2n a0 = 20 = 1. By the definition of the sequence a0 = 1, hence P(0) is true. 2. Inductive step: Show that P(k)  P(k+1) is true P(k) : ak = 2k P(k+1) : ak+1 = 2k+1 Assume that P(k) is true. Show that P(k+1) is also true. By definition of the sequence, ak+1 = 2* ak (this is called recurrence relation) By the assumption that P(k) is true, we have ak = 2k Substitute ak in the expression for ak+1 : ak+1 = 2* ak = 2 * 2k = 2k+1 Hence P(k+1) : ak+1 = 2k+1 is also true. By the principle of mathematical induction it follows that for any integer n, P(n) is true, i.e. for any integer n, an = 2n Example 2: Find the sum of the natural numbers 1, 2, 3, 4, 5, 6,…, n Let Sn be the sum of 1, 2, 3, 4…, n: Sn =1 + 2 + …. + n Prove that Sn = n(n+1)/2 using mathematical induction. i.e. prove P(n): Sn = n(n+1)/2 Proof: Proof outline: We will consider the sequence S1, S2, … Sn, …, find the recurrence relation, and then use the recurrence relation in the proof by mathematical induction.4 1. Find the recurrence relation in the sequence S1, S2, … Sn, … n Sn, n = 1, 2, 3, …. Recurrence relation: 1 1 S1 2 1 + 2 S2 = S1 + 2 3 1 + 2 + 3 S3 = S2 + 3 4 1 + 2 + 3 + 4 S4 = S3 + 4 ….. k 1 + 2 + …+ k Sk = Sk-1 + k… k+1 1 + 2 + ..+k + (k+1) Sk+1 = Sk + (k+1) …. 2. Proof by mathematical induction Step 1. Inductive base. Show that P(1) is true, i.e. S1 = 1*2 / 2 = 1 By the definition of the sequence, S1 = 1. Therefore P(1) is true Step 2. Inductive step. Show that the conditional P(k)  P(k+1) is true, i.e. if Sk = k(k+1)/2 then Sk+1 = (k+1)(k+2)/2 k = 1, 2, 3, … Assume that P(k) is true, i.e. for some k, Sk = k(k+1)/2 Show that P(k+1) is true, i.e. Sk+1 = (k+1)(k+2)/2 We use the recurrence relation between Sk and Sk+1 .: Sk+1 = Sk + (k+1) Sk+1 = Sk + (k+1) = k(k+1)/2 + (k+1) = k(k+1)/2 + 2(k+1)/2 = = (k(k+1) +2(k+1))/2 = (k+1)(k+2)/2 Hence if Sk = k(k+1)/2 then Sk+1 = (k+1)(k+2)/2 Inductive conclusion: for all n, the sum of the first n integers is n(n+1)/25 Example 3: Find the sum of the first n odd numbers 1, 3, 5, …, 2n-1 Let Sn be the sum of 1, 3, 5…, 2n-1 We will prove that Sn = n2 1. Find the recurrence relation in the sequence S1, S2, … Sn, … n Sn, n = 1, 2, 3, … Recurrence relation: 1 1 1 S1 2 1 + 3 4 S2 = S1 + 3 3 1 + 3 + 5 9 S3 = S2 + 5 ….. k 1 + 2 + …+ 2k-1 Sk = Sk-1 + 2k-1 k+1 1 + 2 + ..+ (2k-1) + 2(k+1)-1 Sk+1 = Sk + 2(k+1) - 1 = Sk + (2k+1) …. 2. Proof by mathematical induction Step 1. Inductive base. Show that P(1) is true, i.e. S1 = 12 = 1 By the definition of the sequence, S1 = 1. Therefore P(1) is true Step 2. Inductive step. Show that the conditional P(k)  P(k+1) is true, i.e. if Sk = k2 then Sk+1 = (k+1)2 k = 1, 2, 3, … Assume that for some k, Sk = k2 Show that Sk+1 = (k+1)2 We use the recurrence relation between Sk and Sk+1: Sk+1 = Sk + (2k+1) = = k2 + (2k+1) = k2 + 2k+1 = (k+1)2 Hence if Sk = k2 then Sk+1 = (k+1)2 Inductive conclusion: for all n, the sum of the first n odd integers is