Mathematical Induction PDF

MATHEMATICAL INDUCTION Let 𝑷𝒏 be a statement in terms of 𝒏 where 𝒏 is a positive integer. If: 1. 𝑷𝟏 is true, and 2. the truth of 𝑷𝒌 implies the truth of 𝑷𝒌+𝟏 , for every positive integer 𝒌, then 𝑷𝒏 is true for every positive integer 𝒏 Using the principle of mathematical induction, a proof...

MATHEMATICAL INDUCTION Let 𝑷𝒏 be a statement in terms of 𝒏 where 𝒏 is a positive integer. If: 1. 𝑷𝟏 is true, and 2. the truth of 𝑷𝒌 implies the truth of 𝑷𝒌+𝟏 , for every positive integer 𝒌, then 𝑷𝒏 is true for every positive integer 𝒏 Using the principle of mathematical induction, a proof that some statement is true for all positive integers consists of two parts.  First, we must show that the statement is true for the positive integer 1.  Then we must show that if the statement is true for some positive integer, then it follows that it is also true for the next positive integer. Example 1 Prove that 𝟐𝒏 > 𝒏 for all positive integer values of 𝒏  Part 1: If 𝑛 = 1, then 2𝑛 > 𝑛 becomes 21 > 1, which is a true statement.  Part 2: We must prove the statement, “If 2𝑘 > 𝑘, then 2𝑘+1 > 𝑘 + 1 for all positive integer values of 𝑘”. This can be done as follows: 2𝑘 > 𝑘 Multiply both sides by 2: 2(2𝑘 ) > 2(𝑘) ⇒ (2𝑘+1 ) > 2𝑘 Note: 𝑘 > 1, since we are working with positive integers. Therefore, adding 𝑘 to both sides, we have 𝑘 + 𝑘 ≥ 𝑘 + 1 or 2𝑘 ≥ 𝑘 + 1 Since 2𝑘+1 > 2𝑘 and 2𝑘 ≥ 𝑘 + 1 Then by the transitive property, we can conclude that 2𝑘+1 > 𝑘 + 1 Example 2 Prove that 𝑆𝑛 = 𝑛(𝑛 + 1) for the sequence 𝑎𝑛 = 2𝑛, where n is any positive integer.  Part 1: If n = 1, then 1(1+1) = 2 and 2 is the first term of the sequence 𝑎𝑛 = 2𝑛, so 𝑆1 = 𝑎1 = 2  Part 2: We need to prove that if 𝑆𝑘 = 𝑘(𝑘 + 1), then 𝑆𝑘+1 = (𝑘 + 1)(𝑘 + 2) Using the property of 𝑆𝑘+1 = 𝑆𝑘 + 𝑎𝑘+1, we can then proceed as follows: 𝑆𝑘+1 = 𝑆𝑘 + 𝑎𝑘+1 But 𝑆𝑘 = 𝑘(𝑘 + 1), and 𝑎𝑘+1 = 2(𝑘 + 1) ⇒ 𝑆𝑘+1 = 𝑘(𝑘 + 1) + 2(𝑘 + 1) = 𝑘 2 + 3𝑘 + 2 Factorize 𝑘 2 + 3𝑘 + 2 ⇒ 𝑆𝑘+1 = (𝑘 + 1)(𝑘 + 2) Example 3 𝟓𝒏(𝒏+𝟏) For the sequence 𝒂𝒏 = 𝟓𝒏, prove that 𝑺𝒏 = , where n is any positive integer. 𝟐 5(1)(1+1)  Part 1: Since = 5 and 5 is the first term of the sequence 𝑎𝑛 = 5𝑛, we have 2 𝑆1 + 𝑎1 = 5 5k(k+1) 5(k+1)(k+1+1)  Part 2: We need to prove that if Sk = , then Sk+1 = , 2 2 5k(k+1) 5k(k+1) But, Sk+1 = Sk + ak+1 = 2 +5(k+1) = 2 +5k+5 5k(k+1)+2(5k+5) 5k2 +5k+10k+10) Sk+1= = 2 2 5(k2 +3k+2) 5(k+1)(k+2) Sk+1= = 2 2 Example 4 Prove that for all positive integers 𝒏, the number 32𝑛 − 1 is divisible by 8.  Part 1: If 𝒏 = 𝟏, then 32𝑛 − 1, becomes 32(1) − 1 = 32 − 1 = 8, which is divisible by 8  Part 2: we need to prove the statement, “if 32𝑘 − 1 is divisible by 8, then 32(𝑘+1) − 1 is divisible by 8 for all integer values of 𝑘. This can be verified as follows: 32𝑘 −1 If 32𝑘 − 1 is divisible by 8, then for some integer 𝒙, we have = 𝑥, or 32𝑘 − 1 = 8𝑥 8 Therefore, 32𝑘 − 1 = 8𝑥, or 32𝑘 = 1 + 8𝑥 Multiply both sides by 32 : ( 32 )32𝑘 = (32 )(1 + 8𝑥) ⇒ 32𝑘+2 = 9(1 + 8𝑥) or 32𝑘+2 = 9 + 9(8𝑥) But 9 = 1 + 8) ⇒ 32𝑘+2 = 9 + 9(8𝑥) = 1 + 8 + 9(8𝑥) Applying the distributive property to 8 + 9(8𝑥); ⇒ 32𝑘+2 = 1 + 8(1 + 9𝑥) Hence 32𝑘+2 − 1 = 8(1 + 9𝑥). Therefore 32𝑘 − 1 is divisible by 8 Example 5 Prove by contradiction that if n is an integer, then 𝒏𝟑 − 𝒏 is even. Since every integer 𝒏 is either odd or even, we will consider two cases If 𝒏 is even: Then 𝑛 = 2𝑚, for some integer 𝒎. Therefore 𝑛3 − 𝑛 = (2𝑚)3 − 2𝑚 = 8𝑚3 − 2𝑚 = 2(4𝑚3 − 𝑚), which is even If 𝒏 is odd: Then 𝑛 = 2𝑚 + 1, for some integer 𝒎 Hence 𝑛3 − 𝑛 = (2𝑚 + 1)3 − (2𝑚 + 1) = (8𝑚3 + 12𝑚2 + 6𝑚 + 1) − (2𝑚 + 1), = (8𝑚3 + 12𝑚2 + 4𝑚) = 2(4𝑚3 + 6𝑚2 + 2𝑚), which is even Since 𝒏𝟑 − 𝒏 is even in both cases, we conclude that: 𝒏𝟑 − 𝒏 is even for all integers 𝒎  Note: Mathematical Induction is often used to verify algorithms. To illustrate this, we will verify the polynomial evaluation algorithm 𝑃(𝑥) = 𝑎𝑚 𝑥 𝑚 + 𝑎𝑚−1 𝑥 𝑚−1 + ⋯ + 𝑎1 𝑥 + 𝑎0  Step 1: Let 𝑇 = 𝑎0 and 𝑘 = 1,  Step 2: While 𝑘 ≤ 𝑚, replace 𝑇 by 𝑇 + 𝑎𝑘 𝑥 𝑘 and 𝑘 by 𝑘 + 1  Step 3: 𝑃(𝑥) = 𝑇 Let 𝑺(𝒏) be the following statement: If the replacements 𝑇 by 𝑇 + 𝑎𝑘 𝑥 𝑘 and 𝑘 by 𝑘 + 1 are executed exactly n times each, then 𝑇 = 𝑎𝑛 𝑥 𝑛 + 𝑎𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0 Now, we have to prove that 𝑺(𝒏) is true for all nonnegative integers n  Part 1; If n = 0, then the replacements in step 2 are not performed, so the value of 𝑻 is the value of 𝑎0 given in step 1. But the equality 𝑻 = 𝒂𝟎 is the statement 𝑺(𝟎); so 𝑺(𝟎) is true.  Part 2: To perform the inductive step, we assume that 𝑺(𝒌) is true for some positive integer k and show that 𝑺(𝒌 + 𝟏) is also true. For 𝑺(𝒌) to be true means that 𝑻 = 𝑎𝑘 𝑥 𝑘 + 𝑎𝑘−1 𝑥 𝑘−1 + ⋯ + 𝑎1 𝑥 + 𝑎0 when the replacements in step 2 are executed exactly k times. If the replacements in step 2 are executed one more time (k + 1), then the value of t is: 𝑻 + 𝑎𝑘+1 𝑥 𝑘+1 = (𝑎𝑘 𝑥 𝑘 + 𝑎𝑘−1 𝑥 𝑘−1 + ⋯ + 𝑎1 𝑥 + 𝑎0 ) + 𝑎𝑘+1 𝑥 𝑘+1 Thus 𝑺(𝒌 + 𝟏) is true , completing the inductive step. Since both part 1 and part 2 are true, the principle of mathematical induction guarantees that 𝑺(𝒏) is true for all nonnegative integers n. In particular 𝑺(𝒎). But 𝑺(𝒎) is the statement 𝑃(𝑥) = 𝑇 Exercise 1. Use mathematical induction to prove that each of the following statements is true a. 4𝑛 − 1 is divisible by 3 b. 2𝑛 ≥ 𝑛 + 1 c. 𝑛2 + 𝑛 is divisible by 2 2. Prove by mathematical induction that: 𝟑𝒏𝟐 +𝟕 a. 𝟓 + 𝟖 + 𝟏𝟏 + ⋯ + (𝟑𝒏 + 𝟐) = for any positive integer n 𝟐 𝑛(𝑛+1)(𝑛+2) b. 𝑆𝑛 = for 𝑎𝑛 = 𝑛(𝑛 + 1) 3 c. 𝑆𝑛 = 𝑛2 for 𝑎𝑛 = 2𝑛 − 1)  GROUPS A group is a set G and a binary operation * with the following four properties. i. Closure – for all elements a and b in G, 𝒂 ∗ 𝒃 ∈ 𝑮 ii. Identity – there is an element e in G such that 𝒂 ∗ 𝒃 = 𝒆 ∗ 𝒂 = 𝒂, for all elements a in G iii. Inverses – for each element a in G, there is an element 𝑎−1 in G such that 𝒂 ∗ 𝒂−𝟏 = 𝒂−𝟏 ∗ 𝒂 = 𝒆 iv. Associativity – for all elements a, b and c in G, (𝒂 ∗ 𝒃) ∗ 𝒄 = 𝒂 ∗ (𝒃 ∗ 𝒄) Consider the set 𝐺 = {1, 2, 3} and ∗ defined by addition mod 4 + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2  The set is closed since it forms a Latin Square  Since the set is a set of real numbers and the operation is addition, it has an identity element, 0  Each element has an inverse, eg inverse of 0 is 0; 1 is 3; 2 is 2; 3 is 1  Since the set is driven from ordinary arithmetic it satisfies the associative property Example: Determine whether or not {1, 2, 3, 4, 5, 6} under multiplication modulo 7 forms a group. For {1, 2, 3, 4, 5, 6} under multiplication modulo 7 to forms a group, it must be closed, have an identity element, have an inverse and satisfy the associative property  X (Mod 7) 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1  Closed since it forms a Latin Square  Has an identity element, 1  Has an inverse, eg inverse of 1 is 1, 2 is 4, 3 is 5, 4 is 2, etc  Satisfies the associative property Try: Show that the set {1, 2, 3} under multiplication mod 4 does not form a group.