235-Ch5-1-Induction离散数学英文版

1、Chapter 5: Induction and Recursion (Part 1),Elements of Discrete Structures,Climbing an Infinite Ladder,We can reach step 1. If we can reach step k, we can reach step k + 1. Then, we can reach any step n,Mathematical Induction,For a propositional function P(n) and any integers n b, b is a starting v

2、alue of n in N (Basis Step) we prove: P(b) is true (Inductive Step) and we prove P(k) P(k+1) for any positive integer k Conclusion: P(n) is true Formally:P(b) kZ+(P(k) P(k+1) nN P(n),Understanding Mathematical Induction,Let n be 100. Then, is P(100) true? We may use “modus ponens” 99 times. We can t

3、hen say, yes. P(1) (we prove P(1) is true) P(1) P(2) (k = 1, P(k) P(K+1) P(2)(modus ponens) P(2) P(3)(k = 2, P(k) P(K+1) P(3) (modus ponens) P(99) P(99) P(100) (k = 99, P(k) P(K+1) P(100) (modus ponens),Remembering How Mathematical Induction Works,Consider an infinite sequence of dominoes, labeled 1

4、, 2, 3, , where each domino is standing.,We know that the first domino is knocked down, i.e., P(1) is true . We also know that if whenever the kth domino is knocked over, it knocks over the (k + 1)st domino, i.e, P(k) P(k + 1) is true for all positive integers k.,Let P(n) be the proposition that the

5、 nth domino is knocked over.,Hence, all dominos are knocked over. P(n) is true for all positive integers n.,Induction Examples for Summation,Example 1. Prove that the equation is trueP(n): 1 + 2 + 3 + + n = n(n + 1)/2 Proof by induction (on blackboard) Example 2. Prove that the equation is trueP(n):

6、 1 + 3 + 5 + . + (2n 1) = n2 Proof by induction (on blackboard) Example 3. Prove that the equation is trueP(n): a + ar1 + ar2 + + arn = (arn+1 a)/(r 1) Proof by induction (on blackboard),Inequality Example,Prove that n 2n for positive integers n. Basis step: P(1): 1 21 Inductive step: assume P(k) is

7、 correct, prove P(k+1) is correct, for all positive k.k 2k (assumption)k+1 2k + 1 (from assumption) 2k + 2k = 2k+1,Inequality Example,Prove that 2n n! for integers n 4 Basis step: P(4) = 24 = 16 4! = 4321 = 24 Inductive step: Assume 2k k! for k 4, then 2k+1 = 22k 2k! (k + 1)k! = (k + 1)! So, 2k+1 (k

8、 + 1)!,Harmonic numbers Hj, j = 1, 2, 3, . are defined by Prove that Basis step: when n =1, Inductive step: Continued on the blackboard,Harmonic Numbers,Divisibility Example,Prove that n3 n is divisible by 3 for all positive integer n Basis step: when n = 1, 13 1 = 0, 3 | 0 Inductive step: when n =

9、k, if k3 k is divisible by 3, then k3 k = 3m for some integer m. For n = k + 1, (k + 1)3 (k + 1) = k3 + 3k2 + 3k k= k3 k + 3(k2 + k) = 3m + 3(k2 + k)= 3(m + k2 + k). So (k + 1)3 (k + 1) is divisible by 3,Number of Subsets Example,Power Set Theorem P(n): a set of n elements has 2n subsets, n is a non

10、negative integer Basis step: P(0) is true because empty set has 20 = 1 subset. (P(1) is also true, ) Inductive step: assume P(k) is true for set S of k elements, so S has 2k subsets. For a set T of k + 1 elements, let T = S a, a S. Each subset X of S is also a subset of T. In addition, X a is also a

11、 subset of T. Total subsets in T = 2k + 2k = 2k+1,Checkerboard Tiling Example,Prove that a checkerboard with 2n 2n squares, where one arbitrary square has been removed, can be tiled with L-shape tiles, each of which covers three adjacent squares Basis: for n = 1, regardless where a square is removed

12、, it can be tiled with an “L”,Checkerboard Tiling Example,Assume the checkerboard of 2k 2k squares with one square removed can be tiled with Ls, Need to prove that the checkerboard of 2k+1 2k+1 squares with one square removed can also be tiled with Ls,Checkerboard Tiling Example,The removed square m

13、ust be in one of the four 2k 2k checkerboards. Assume its in the bottom right one. By assumption, it can be tiled with Ls,2k+1,2k,2k,Then use one L to tile across all other three 2k 2k boards as indicated in the picture Then, take these three squares as removed ones, one from each of the three 2k 2k

14、 boards By assumption they can be tiled with Ls,Strong Induction(强归纳),For a propositional function P(n) and any integer n b, b is a starting value of n in N, (Basis Step) If we prove: P(b) is true (Inductive Step) and we prove that, if P(b)P(b+1) P(k) then P(k+1) for all positive integer k b Then P(

15、n) is true,Strong Induction Example,The Fundamental Theorem of ArithmeticEvery positive integer n 1 is a prime or the product of primes Proof. Basis step: n = 2, it is a prime. Inductive step: Assume integers 2, 3, , k for k 1 are all either a prime or a product of primes. Need to show that k + 1 is

16、 a prime or product of primes. If k + 1 is not a prime (it is composite), then there are integers a and b, 2 a b k + 1 and k + 1 = ab. By assumption a k and b k so they are either primes or products of primes. So is k + 1,Strong Induction Example,Consider the game where there are 2 piles of matches.

17、 Each pile consists of n matches. For two players, each can pick an arbitrary number of matches from just one pile. The one who gets the last matches wins. Show that the second player can always win,Strong Induction Example,Proof. n = 1 (each pile has one match), obviousAssume the second player wins

18、 for n = 1, 2, k. Now each pile has k + 1 matches. If the 1st player takes j matches (1 j k) from one pile, then the 2nd player also takes j matches from the other pile. Now each pile has k + 1 j matches. By assumption, the 2nd player wins,Postage Example 1,Prove that the amount of postage of 12 cen

19、ts or more can be formed using just 4-cent and 5-cent stamps Mathematical Induction proofWhen n =12 (basis step), three 4-cent stamps form 12 centsIf n = k is true, for the k + 1 cent postage, its either from replacing a 4-cent stamp (if there is one) in the k-cent postage with a 5-cent one. Otherwi

20、se, there must be at least three 5-cent stamps (why?). Replace them with four 4-cent ones,Postage Example 1,Prove that the amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps Strong Induction proofWhen n = 12, 13, 14 and 15, they can be formed by 4-cent and 5-cent

21、 stampsAssume it is true for n = 12, 13, 14, 15, , k 3, k 2, k 1, k (k 15). For the k + 1 cent postage, since k 3 is true, from which we just add a 4-cent stamp to get to a k + 1 cent postage,Postage Example 2,Exercise 6 (P.342 of textbook): Determine the x, such that all postage x can be formed usi

22、ng just 3-cent and 10-cent stamps Answer: Try to find 3, 6, 9, 10, 13, 15, 16, 18, and larger postage can be formed by 3 and10 combinations Prove your answer to a) using mathematical induction Proof: Basis: 18 cent postage = 6 3-cent Inductive: Assume k-cent postage can be formed from 3-cent and 10-

23、cent stamps. Need to prove that k + 1-cent postage can be formed from 3-cent and 10-cent stamps,Postage Example 2,Proof: (continued) If the k-cent postage includes three or more 3-cent stamps, then we replace 33-cent stamps by 110-cent stamp, so that k + 1-cent postage can be formed from 3-cent and

24、10-cent stamps. Otherwise, the k-cent postage only includes 23-cent, 13-cent, or no 3-cent stamps In the 1st case (23), k = 6 + 10m (m 2 since the postage 18 cents). We replace 20 (210) by 21 (37) to form k + 1 as follows: 39 + 10(m 2). So, k + 1 is formed from only 3-cent and 10-cent stamps,Need Ch

25、ange,Postage Example 2,Proof: (continued) In the 2nd case (13), k = 3 + 10m (m 2 since the postage 18 cents). We replace 210 by 37 to form k + 1 as follows: 38 + 10(m 2). So, k + 1 is formed from only 3-cent and 10-cent stamps In the last case (no 3s), k = 10m (m 2 since the postage 18 cents). We re

26、place 20 by 21 (37) to form k + 1 as follows: 37 + 10(m 2). So, k + 1 is formed from only 3-cent and 10-cent stamps,Postage Example 2,Prove your answer to a) using strong induction Proof: Basis: 18 = 6 3; 19 = 3 3 + 10; 20 = 2 10 Inductive: Assume for all j, 18 j k (k 20), j-cent postage can be form

27、ed from 3-cent and 10-cent stamps. Need to prove that k + 1-cent postage can be formed from 3-cent and 10-cent stamps Since (k 2)-cent postage (k 2 18) can be formed from 3-cent and 10-cent stamps (inductive step), we add a 3-cent stamp to form (k + 1)-cent postage,Math. Induction vs. Strong Inducti

28、on,Mathematical Induction and Strong Induction are in fact equivalent This is because, from mathematical induction， P(1) and P(k) P(k+1) for any k, we can apply modus ponent law k-1 times to get P(2) P(3) . P(k-1),The Well-Ordering Property(良序性),Every non-empty set of nonnegative integers has a smal

29、lest element (A trivial statement made explicit so we can give it a name in a proof),Round-Robin Tournament(循环赛) Example,n players play against each other. A cycle is a situation where p1 beats p2, p2 beats p3, , pm beats p1, m n, pi is player i No tie (配合) is allowed in the game Proposition: If the

30、re is a cycle of m and m 3, then there is also a cycle of exactly 3 among these players,Round-Robin Tournament Example,Proof by contradiction. Assume that there is a cycle of length k, where k is the smallest integer 3 (well-ordering property) for which a cycle exist and no cycle of length 3 exists

31、Cycle: p1 p2 p3 . pk (k 3, p1 beats p2 pk beats p1) Look at p1 p2 p3, if p3 beats p1 we have a cycle of length 3 (contradiction). Otherwise, it must be the case that p1 beat p3 we can construct the cycle p1 p3 p4 . pk which leads to a cycle of length k 1. This contradicts to the fact that k is alrea

32、dy the smallest length of a cycle,Proving the Division Algorithm,If a is an integer and d is a positive integer, then there are unique integers q and 0 r d such that a = dq + r, or a dq = r Proof : (a) There exist such r. Let S = a dq | a dq 0 for q Z. Then, from the well-ordering property S has the

33、 smallest element r, r = a dq0 for some integer q0. Then r must be d, otherwise, r d, or a dq0 d, or a d(q0 +1) 0. So r1 = a d(q0 +1) is in S and smaller than r = a dq0. Contradiction!,Proving the Division Algorithm,If a is an integer and d is a positive integer, then there are unique integers q and 0 r d such that a = dq + r, or a dq = r Proof continued: (b) r is unique. Assume there are q and r such that a = dq + r = dq + r, 0 r d and 0 r d. Then d(q q) = r r, or d divides r r. But |r r| d. The only way for d to divide r r is r r = 0! r is unique since its the smallest elem