1、Chapter 5: Induction and Recursion (Part 1)Elements of Discrete Structures Climbing an Infinite LadderWe can reach step 1.If we can reach step k, we can reach step k + 1.Then, we can reach any step nMathematical Induction For a propositional function P(n) and any integers n b, b is a starting value
2、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 then sa
3、y, 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 WorksConsider an infinite sequence of dominoes, labeled 1, 2, 3, , wher
4、e 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 nth domino is
5、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): 1 + 3 + 5 + . +
6、(2n 1) = n2 Proof by induction (on blackboard) Example 3. Prove that the equation is trueP(n): a + ar1 + ar2 + + ar n = (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 correct, prove P
7、(k+1) is correct, for all positive k.k 2k (assumption)k+1 2k + 1 (from assumption) 2k + 2k = 2k+1Inequality 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 + 1)! Harmonic nu
8、mbers Hj, j = 1, 2, 3, . are defined by Prove that Basis step: when n =1, Inductive step: Continued on the blackboard Harmonic NumbersDivisibility 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 = 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
