Toán học - Chapter 5: Induction and recursion

Induction and recursionChapter 5With Question/Answer AnimationsCopyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.Chapter SummaryMathematical InductionStrong InductionWell-OrderingRecursive DefinitionsStructural InductionRecursive AlgorithmsProgram Correctness (not yet included in overheads)Mathematical InductionSection 5.1Section SummaryMathematical InductionExamples of Proof by Mathematical InductionMistaken Proofs by Mathematical InductionGuidelines for Proofs by Mathematical InductionClimbing an Infinite LadderSuppose 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.This example motivates proof by mathematical induction.Principle of Mathematical Induction 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 InductionMathematical induction can be expressed as the rule of inference where the domain is the set of positive integers.In a proof by 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. (P(1) ∧ ∀k (P(k) → P(k + 1))) → ∀n P(n), Validity of Mathematical InductionMathematical 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 (see Section 5.2 and Appendix 1). Here is the proof: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 can not be 1 since P(1) holds. Since m is positive and greater than 1, m − 1 must be a positive integer. Since m − 1 0.Therefore, there are integers q and r with 0 ≤ r αn − 2, where α = (1 + √5)/2. Solution: Let P(n) be the statement fn > αn−2 . Use strong induction to show that P(n) is true whenever n ≥ 3.BASIS STEP: P(3) holds since α αj−2 for all integers j with 3 ≤ j ≤ k, where k ≥ 4. Show that P(k + 1) holds, i.e., fk+1 > αk−1 . Since α2 = α + 1 (because α is a solution of x2 − x − 1 = 0),By the inductive hypothesis, because k ≥ 4 we haveTherefore, it follows thatHence, P(k + 1) is true. −2 . fk+1 = fk + fk−1 > αk−2 + αk−3 = αk−1. αk−1 = α2 ∙ αk−3 = ( α + 1) ∙αk−3 = α ∙αk−3+ 1 ∙αk−3 = αk−2 + αk−3 fk−1 > αk−3, fk > αk−2. Why does this equality hold?Lamé’s Theorem Lamé’s Theorem: Let a and b be positive integers with a ≥ b. Then the number of divisions used by the Euclidian algorithm to find gcd(a,b) is less than or equal to five times the number of decimal digits in b. Proof: When we use the Euclidian algorithm to find gcd(a,b) with a ≥ b,Gabriel Lamé(1795-1870)r0 = r1q1 + r2 0 ≤ r2 αn − 1, for n > 2, where α = (1 + √5)/2. Therefore, b > αn−1.Because log10 α ≈ 0.208 > 1/5, log10 b > (n−1) log10 α > (n−1)/5 . Hence,Suppose that b has k decimal digits. Then b b.By Lamé’s Theorem, the number of divisions needed to find gcd(a,b) with a > b is less than or equal to 5 (log10 b + 1) since the number of decimal digits in b (which equals ⌊log10 b⌋ + 1) is less than or equal to log10 b + 1. n−1 0, by the inductive hypothesis we can conclude am,n = am−1,n + 1 = m + n(n − 1)/2 +n = m + n(n + 1)/2 .−2 . Recursive AlgorithmsSection 5.4Section SummaryRecursive AlgorithmsProving Recursive Algorithms CorrectRecursion and Iteration (not yet included in overheads)Merge SortRecursive Algorithms Definition: An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.For the algorithm to terminate, the instance of the problem must eventually be reduced to some initial case for which the solution is known.Recursive Factorial Algorithm Example: Give a recursive algorithm for computing n!, where n is a nonnegative integer. Solution: Use the recursive definition of the factorial function.procedure factorial(n: nonnegative integer)if n = 0 then return 1else return n∙factorial (n − 1){output is n!} Recursive Exponentiation Algorithm Example: Give a recursive algorithm for computing an, where a is a nonzero real number and n is a nonnegative integer. Solution: Use the recursive definition of an.procedure power(a: nonzero real number, n: nonnegative integer)if n = 0 then return 1else return a∙ power (a, n − 1){output is an} Recursive GCD Algorithm Example: Give a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and b with a 0.procedure gcd(a,b: nonnegative integers with a 0 and m ≥ 2, n ≥ 0)if n = 0 then return 1else if n is even then return mpower(b,n/2,m)2 mod melse return (mpower(b,⌊n/2⌋,m)2 mod m∙ b mod m) mod m{output is bn mod m} (see text for full explanation)Recursive Binary Search Algorithm Example: Construct a recursive version of a binary search algorithm. Solution: Assume we have a1,a2,, an, an increasing sequence of integers. Initially i is 1 and j is n. We are searching for x.procedure binary search(i, j, x : integers, 1≤ i ≤ j ≤n)m := ⌊(i + j)/2⌋if x = am then return melse if (x am and j >m) then return binary search(m+1,j,x)else return 0{output is location of x in a1, a2,,an if it appears, otherwise 0} Proving Recursive Algorithms Correct Both mathematical and str0ng induction are useful techniques to show that recursive algorithms always produce the correct output. Example: Prove that the algorithm for computing the powers of real numbers is correct. Solution: Use mathematical induction on the exponent n. BASIS STEP: a0 =1 for every nonzero real number a, and power(a,0) = 1. INDUCTIVE STEP: The inductive hypothesis is that power(a,k) = ak, for all a ≠0. Assuming the inductive hypothesis, the algorithm correctly computes ak+1, since power(a,k + 1) = a∙ power (a, k) = a∙ ak = ak+1 . procedure power(a: nonzero real number, n: nonnegative integer)if n = 0 then return 1else return a∙ power (a, n − 1){output is an}−2 . Merge SortMerge Sort works by iteratively splitting a list (with an even number of elements) into two sublists of equal length until each sublist has one element.Each sublist is represented by a balanced binary tree.At each step a pair of sublists is successively merged into a list with the elements in increasing order. The process ends when all the sublists have been merged.The succession of merged lists is represented by a binary tree.Merge Sort Example: Use merge sort to put the list 8,2,4,6,9,7,10, 1, 5, 3 into increasing order. Solution:Recursive Merge Sort Example: Construct a recursive merge sort algorithm. Solution: Begin with the list of n elements L.procedure mergesort(L = a1, a2,,an )if n > 1 then m := ⌊n/2⌋ L1 := a1, a2,,am L2 := am+1, am+2,,an L := merge(mergesort(L1), mergesort(L2 )){L is now sorted into elements in increasing order} continued → Recursive Merge SortSubroutine merge, which merges two sorted lists. Complexity of Merge: Two sorted lists with m elements and n elements can be merged into a sorted list using no more than m + n − 1 comparisons.procedure merge(L1, L2 :sorted lists)L := empty listwhile L1 and L2 are both nonempty remove smaller of first elements of L1 and L2 from its list; put at the right end of L if this removal makes one list empty then remove all elements from the other list and append them to Lreturn L {L is the merged list with the elements in increasing order} Merging Two Lists Example: Merge the two lists 2,3,5,6 and 1,4. Solution:Complexity of Merge Sort Complexity of Merge Sort: The number of comparisons needed to merge a list with n elements is O(n log n).For simplicity, assume that n is a power of 2, say 2m.At the end of the splitting process, we have a binary tree with m levels, and 2m lists with one element at level m.The merging process begins at level m with the pairs of 2m lists with one element combined into 2m−1 lists of two elements. Each merger takes two one comparison.The procedure continues , at each level (k = m, m−1, m−1,,3,2,1) 2k lists with 2m−k elements are merged into 2k−1 lists, with 2m−k + 1 elements at level k−1.We know (by the complexity of the merge subroutine) that each merger takes at most 2m−k + 2m−k − 1 = 2m−k+ 1 − 1 comparisons.continued → Complexity of Merge SortSumming over the number of comparisons at each level, shows that because m = log n and n = 2m. (The expression in the formula above is evaluated as 2m − 1 using the formula for the sum of the terms of a geometric progression, from Section 2.4.)In Chapter 11, we’ll see that the fastest comparison-based sorting algorithms have O(n log n) time complexity. So, merge sort achieves the best possible big-O estimate of time complexity.