5.3 Recursive Definitions and Structural Induction Mar 19, 2018 Shawn Math 240 No comments yet Math 521 – 3/16 Mar 18, 2018 Shawn Math 521 No comments yet Math 521 – 3/14 Mar 16, 2018 Shawn Math 521 No comments yet 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 1 … 21 22 23 24 25 … 41
![Theorem 2.38 (Nested Intervals Theorem) • Statement ○ If {I_n } is a sequence of closed intervals in R s.t. I_n⊃I_(n+1),∀n∈N ○ Then ⋂24_(n=1)^∞▒I_n is nonempty • Intuition • Proof ○ Let I_n≔[a_n,b_n ] ○ Let E≔{a_n }_(n∈N § E is nonempty § E is bounded above by b_1 since b_1≥a_n,∀n∈N § So supE exists ○ Let x≔supE ○ For m,n∈N, a_n≤a_(m+n)≤b_(m+n)≤b_m § a_n≤b_m⇒x≤b_n,∀m∈N § x=supE⇒a_m≤x,∀m∈N ○ So, x∈[a_m,b_m ],∀m∈N ○ Therefore x∈⋂24_(n=1)^∞▒I_n Theorem 2.39 • Statement ○ Let k be a positive integer ○ If {I_n } is a sequence of k-cells s.t. I_n⊃I_(n+1),∀n∈N ○ Then ⋂24_(n=1)^∞▒I_n is nonempty • Proof ○ Let I_n consists of all points x ⃗=(x_1,x_2,…,x_k ) s.t. ○ a_(n,j)≤x_j≤b_(n,j), where 1≤j≤k,n=1,2,3,… ○ Let I_(n,j)=[a_(n,j),b_(n,j) ] ○ For each j, {I_(n,j) } satisfies the hypothesis of Theorem 2.38 ○ Therefore ∃x_j^∗∈⋂24_(n=1)^∞▒I_(n,j) , for 1≤j≤k ○ Let (x^∗ ) ⃗=(x_1^∗,x_2^∗,…,x_k^∗ ) ○ By construction, (x^∗ ) ⃗∈⋂24_(n=1)^∞▒I_n Theorem 2.40 • Statement ○ Every k-cell is compact • Proof ○ Let I={(x_1,x_2,…,x_k )∈Rk│a_j≤x_j≤b_j,1≤j≤k} be a k-cell ○ Let δ=√(∑_(j=1)^k▒(b_j−a_j )^2 ), then |x ⃗−y ⃗ |≤δ,∀x ⃗,y ⃗∈I ○ Suppose {G_α } is an open cover of I with no finite subcover ○ Build sequence {I_n } § Let c_j=(a_j+b_j)/2 § Consider intervals [a_j,c_j ] and [c_j,b_j ] § Those intervals describes 2^k k-cells Q_i whose union is I § Since the number of Q_i is finite, and {G_α } has no finite subcover § ∃Q_i not covered by a finite subcover of {G_α }; call this I_1 § Repeat this process on I_1 to obtain I_2,I_3,… § We can build a sequence {I_n } ○ {I_n } is a sequence of k-cells s.t. § I⊃I_1⊃I_2⊃… § I_n is not covered by any finite sub-collection of {G_α } § If x ⃗,y ⃗∈I_n, then |x ⃗−y ⃗ |≤δ/2^n ○ By Theorem 2.38, ∃x ⃗^∗∈I_n,∀n∈N ○ Then (x^∗ ) ⃗∈G_α, for some G_α § G_α is open § i.e. ∃r 0 s.t. |y ⃗−(x^∗ ) ⃗ | r⇒y ⃗∈G_α § By Archimedean Property, ∃n∈N s.t. δ/2^n r § In this case, I_n⊂G_α, which is impossible, since § I_n is not covered by any finite sub-collection of {G_α } § So no such open cover {G_α } exists ○ So every open cover of I have a finite subcover ○ Therefore I is compact](https://shawnzhong.com/wp-content/uploads/2018/04/img_5acaeec101efa.png)
![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)
