5.2 Strong Induction and Well-Ordering Mar 14, 2018 Shawn Math 240 No comments yet 5.1 Mathematical Induction Mar 14, 2018 Shawn Math 240 No comments yet
![Strong Induction • To prove that P(n) is true for all positive integers n • where P(n) is a propositional function, complete two steps: • Basis Step ○ Verify that the proposition P(1) is true. • Inductive Step ○ Show the conditional statement § [P(1)∧P(2)∧…∧P(k)]→ P(k+1) ○ holds for all positive integers k. • Strong Induction is sometimes called ○ the second principle of mathematical induction ○ complete induction Proof using Strong Induction • Prove that every natural number n 7 can be written as 3p+5q • where p and q are natural numbers • Prove this result using strong induction • Basis Step ○ 8=3×1+5×1 • Inductive Step ○ Inductive hypothesis: The statement is true for any n for k≥n≥8 ○ In particular it is true for k+1−3 (assuming k+1−3≥8) ○ So k+1−3=3p+5q and so k+1=3(p+1)+5q • What happens if k+1=9 or k+1=10? ○ Add those cases into the basis step ○ 9=3×3+5×0 ○ 10=3×0+5×2 Which Form of Induction Should Be Used? • We can always use strong induction instead of mathematical induction. • But there is no reason to use it if it is simpler to use mathematical induction • In fact, the principles of mathematical induction, strong induction, and the well-ordering property are all equivalent. • Sometimes it is clear how to proceed using one of the three methods, but not the other two. Proof of the Fundamental Theorem of Arithmetic • Show that if n is an integer greater than 1 • Then n can be written as the product of primes. • Let P(n) be the proposition that n can be written as a product of primes. • Basis Step ○ P(2) is true since 2 itself is prime. • Inductive Step ○ The inductive hypothesis is P(j) is true for j∈Z with 2≤j≤k ○ To show that P(k+1) must be true under this assumption ○ Two cases need to be considered: ○ If k+1 is prime, then P(k+1) is true. ○ Otherwise, k+1 is composite ○ And it can be written as the product of two positive integers ○ a and b with 2≤a≤b≤k+1 ○ By inductive hypothesis a and b can be written as product of primes ○ Therefore k + 1 can also be written as the product of those primes. • Hence, every integer greater than 1 can be written as product of primes Well-Ordering Property • Well-ordering property ○ Every nonempty set of nonnegative integers has a least element. • The well-ordering property is one of the axioms of the positive integers • The well-ordering property can be used directly in proofs. • The well-ordering property can be generalized. • Definition: A set is well ordered if every subset has a least element. ○ N is well ordered under ≤. ○ The set of finite strings over an alphabet using lexicographic ordering is well ordered. Proof of The Division Algorithm • Use the well-ordering property to prove the division algorithm ○ If a is an integer and d is a positive integer, then ○ there are unique integers q and r with 0≤r d, such that ○ a=dq+4 • Let S be the set of nonnegative integers of the form a=dq, q∈Z. • The set is nonempty since −dq can be made as large as needed • By the well-ordering property, S has a least element r=a−dq_0 • The integer r is nonnegative. • It also must be the case that r d • If it were not, then there would be a smaller nonnegative element in S ○ a−d(q_0+1)=a−dq_0−d=r−d 0 • Therefore, there are integers q and r with 0≤r d](https://shawnzhong.com/wp-content/uploads/2018/03/img_5aa936280eb33.png)
![Climbing an Infinite Ladder • Suppose we have an infinite ladder: ○ We can reach the first rung of the ladder. ○ If we can reach a particular rung of the ladder ○ then we can reach the next rung. • From (1), we can reach the first rung. • Then by applying (2), we can reach the second rung. • Applying (2) again, the third rung. And so on. • We can apply (2) any number of times to reach any particular rung, no matter how high up. Principle of Mathematical Induction • To prove that P(n) is true for all positive integers n, we complete these steps: ○ Basis Step: Show that P(1) is true. ○ Inductive Step: Show that P(k)→P(k+1) is true for all positive integers k • To complete the inductive step ○ assuming the inductive hypothesis that P(k) holds for an arbitrary integer k ○ show that must P(k+1) be true. • Climbing an Infinite Ladder Example: ○ Basis Step § By (1), we can reach rung 1. ○ Inductive Step § Assume the inductive hypothesis that we can reach rung k § Then by (2), we can reach rung k+1. ○ Hence, P(k)→P(k+1) is true for all positive integers k ○ We can reach every rung on the ladder. Important Points About Using Mathematical Induction • Mathematical induction can be expressed as the rule of inference ○ (P(1)∧∀k(P(k)→P(k+1)))→∀n P(n) ○ where the domain is the set of positive integers. • In mathematical induction, we don’t assume that P(k) is true for all positive integers! • We show that if we assume that P(k) is true, then P(k+1) must also be true. • Proofs by mathematical induction do not always start at the integer 1. • In such a case, the basis step begins at a starting point b where b is an integer. • We will see examples of this soon. Proving a Summation Formula by Mathematical Induction • Example ○ Show that:∑_(i=1)^n▒i=n(n+1)/2 • Solution ○ Basis Step § P(1) is true since 1(1+1)/2=1 ○ Inductive Step § Assume true for P(k) § The inductive hypothesis is ∑_(i=1)^k▒i=k(k+1)/2 § Under this assumption § 1+2+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2 Validity of Mathematical Induction • Mathematical induction is valid because of the well ordering property, which states that • every nonempty subset of the set of positive integers has a least element • Suppose that P(1) holds and P(k)→P(k+1) is true for all positive integers k. • Assume there is at least one positive integer n for which P(n) is false. • Then the set S of positive integers for which P(n) is false is nonempty. • By the well-ordering property, S has a least element, say m. • We know that m cannot be 1 since P(1) holds. • Since m is positive and greater than 1, m−1 must be a positive integer. • Since m−1 m, it is not in S, so P(m−1) must be true. • But then, since the conditional P(k)→P(k+1) for every positive integer k holds, • P(m) must also be true. This contradicts P(m) being false. • Hence, P(n) must be true for every positive integer n. Conjecturing and Proving Correct a Summation Formula • Example ○ Conjecture and prove correct a formula for the sum of the first n positive odd integers ○ Then prove your conjecture • Solution ○ We have § 1= 1 § 1 + 3 = 4 § 1 + 3 + 5 = 9 § 1 + 3 + 5 + 7 = 16 § 1 + 3 + 5 + 7 + 9 = 25. ○ We can conjecture that the sum of the first n positive odd integers is n^2, § 1+3+5+…+(2n−1)+(2n+1)=n^2 ○ We prove the conjecture is proved correct with mathematical induction. ○ Basis Step § P(1) is true since 1^2 = 1. ○ Inductive Step: P(k)→P(k+1) for every positive integer k. § Inductive Hypothesis: 1+3+5+…+(2k−1)=k^2 § So, assuming P(k), it follows that: § 1+3+5+…+(2k−1)+(2k+1) § =[1+3+5+…+(2k−1)]+(2k+1) § =k^2+(2k+1) § =(k+1)^2 ○ Hence, we have shown that P(k+1) follows from P(k). ○ Therefore the sum of the first n positive odd integers is n^2 Proving Inequalities • Example ○ Use mathematical induction to prove that n 2^n for all positive integers n. • Solution ○ Let P(n) be the proposition that n 2^n. ○ Basis Step § P(1) is true since 1 2^1 = 2. ○ Inductive Step § Assume P(k) holds, i.e., k 2^k, for an arbitrary positive integer k. § Must show that P(k + 1) holds. § Since by the inductive hypothesis, k 2^k, it follows that: § k+1 2^k+1≤2^k+2^k=2⋅2^k=2^(k+1) § Therefore n 2^n holds for all positive integers n. • Example ○ Use mathematical induction to prove that 2^n n!, for every integer n≥4 • Solution ○ Let P(n) be the proposition that 2^n n! ○ Basis Step § P(4) is true since 24 = 16 4! = 24 ○ Inductive Step § Assume P(k) holds, i.e., 2^k k! for an arbitrary integer k ≥ 4. § To show that P(k+1) holds § 2^(k+1)=2∙2^k 2⋅2^k (k+1)k!=(k+1)! § Therefore, 2^n n! holds, for every integer n ≥ 4 Proving Divisibility Results • Example ○ Use mathematical induction to prove that n^3−n is divisible by 3 ○ for every positive integer n. • Solution ○ Let P(n) be the proposition that n^3−n is divisible by 3. ○ Basis Step § P(1) is true since 13 − 1 = 0, which is divisible by 3 ○ Inductive Step § Assume P(k) holds, i.e., k^3−k is divisible by 3, for an arbitrary positive integer k § To show that P(k + 1) follows § (k+1)^3−(k+1)=(k^3+3k^2+3k+1)−(k+1)=(k^3−k)+3(k^2+k) § By the inductive hypothesis, the first term (k^3−k) is divisible by 3 § and the second term is divisible by 3 since it is an integer multiplied by 3. § So by part (i) of Theorem 1 in Section 4.1, (k+1)^3−(k+1) is divisible by 3 ○ Therefore, n^3−n is divisible by 3, for every integer positive integer n. Number of Subsets of a Finite Set • Example ○ Use mathematical induction to show that if S is a finite set with n elements ○ where n is a nonnegative integer, then S has 2^n subsets. ○ (Chapter 6 uses combinatorial methods to prove this result.) • Solution ○ Let P(n) be the proposition that a set with n elements has 2^n subsets. ○ Basis Step § P(0) is true, because the empty set has only itself as a subset and 2^0 = 1. ○ Inductive Step § Assume P(k) is true for an arbitrary nonnegative integer k. § Inductive Hypothesis § For an arbitrary nonnegative integer k, every set with k elements has 2^k subsets § Let T be a set with k+1 elements § Then T=S∪{a}, where a∈T and S=T−{a}. Hence |S| = k. § For each subset X of S, there are exactly two subsets of T, i.e., X and X∪{a}. § By the inductive hypothesis S has 2^k subsets. § Since there are two subsets of T for each subset of S, § the number of subsets of T is 2⋅2^k=2^(k+1) An Incorrect “Proof” by Mathematical Induction • P(n)≔every set of n lines in the plane, no two of which are parallel, meet in a point • Here is a “proof” that P(n) is true for all positive integers n≥2. • Basis Step ○ The statement P(2) is true ○ because any two lines in the plane that are not parallel meet in a common point. • Inductive hypothesis ○ P(k) is true for the positive integer k ≥ 2 ○ every set of k lines in the plane, no two of which are parallel, meet in a common point. • Inductive Step ○ We must show that if P(k) holds, then P(k+1) holds ○ If every set of k lines in the plane, no two of which are parallel, k ≥ 2, meet in a point ○ Then every set of k+1 lines in the plane, no two of which are parallel, meet in a point. ○ Consider a set of k + 1 distinct lines in the plane, no two parallel. ○ By the inductive hypothesis, the first k of these lines must meet in a common point p_1. ○ By the inductive hypothesis, the last k of these lines meet in a common point p_2. ○ If p_1 and p_2 are different points, all lines containing both of them must be the same line since two points determine a line. ○ This contradicts the assumption that the lines are distinct. ○ Hence, p_1=p_2 lies on all k + 1 distinct lines, and therefore P(k+1) holds. ○ Assuming that k ≥ 2, distinct lines meet in a common point ○ Then every k + 1 lines meet in a common point. • There must be an error in this proof since the conclusion is absurd. But where is the error? ○ P(k)→P(k+1) only holds for k≥3 ○ It is not the case that P(2) implies P(3) ○ The first two lines must meet in a common point p_1 and the second two must meet in a common point p_2 ○ They do not have to be the same point since only the second line is common to both sets of lines.](https://shawnzhong.com/wp-content/uploads/2018/03/img_5aa92c5c396c9.png)
