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 2k+1≤2k+2k=2⋅2k=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∙2k 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)=(k3+3k2+3k+1)−(k+1)=(k3−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⋅2k=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.
