1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 15Milos [email protected] Sennott SquareMathematical induction& RecursionM. HauskrechtCS 441 Discrete mathematics for CSProofsBasic proof methods: • Direct, Indirect, Contradiction, By Cases, EquivalencesProof of quantified statements:• There exists x with some property P(x).– It is sufficient to find one element for which the property holds.• For all x some property P(x) holds.– Proofs of ‘For all x some property P(x) holds’ must cover all x and can be harder.• Mathematical induction is a technique that can be applied to prove the universal statements for sets of positive integers or their associated sequences.2M. HauskrechtCS 441 Discrete mathematics for CSMathematical induction• Used to prove statements of the form x P(x) where x  Z+Mathematical induction proofs consists of two steps:1) Basis: The proposition P(1) is true.2) Inductive Step: The implication P(n)  P(n+1), is true for all positive n.• Therefore we conclude x P(x).• Based on the well-ordering property: Every nonempty set of nonnegative integers has a least element.M. HauskrechtCS 441 Discrete mathematics for CSMathematical inductionExample: Prove the sum of first n odd integers is n2.i.e. 1 + 3 + 5 + 7 + ... + (2n - 1) = n2for all positive integers.Proof:• What is P(n)? P(n): 1 + 3 + 5 + 7 + ... + (2n - 1) = n2Basis Step Show P(1) is true• Trivial: 1 = 12Inductive Step Show if P(n) is true then P(n+1) is true for all n.• Suppose P(n) is true, that is 1 + 3 + 5 + 7 + ... + (2n - 1) = n2• Show P(n+1): 1 + 3 + 5 + 7 + ... + (2n - 1) + (2n + 1) =(n+1) 2follows:• 1 + 3 + 5 + 7 + ... + (2n - 1) + (2n + 1) =n2+ (2n+1) = (n+1)23M. HauskrechtCS 441 Discrete mathematics for CSCorrectness of the mathematical inductionSuppose P(1) is true and P(n)  P(n+1) is true for all positive integers n. Want to show x P(x).Assume there is at least one n such that P(n) is false. Let S be the set of nonnegative integers where P(n) is false. Thus S . Well-Ordering Property: Every nonempty set of nonnegative integers has a least element.By the Well-Ordering Property, S has a least member, say k. k > 1, since P(1) is true. This implies k - 1 > 0 and P(k-1) is true (since k is the smallest integer where P(k) is false).Now: P(k-1)  P(k) is truethus, P(k) must be true (a contradiction).• Therefore x P(x).M. HauskrechtCS 441 Discrete mathematics for CSMathematical inductionExample: Prove n < 2nfor all positive integers n.• P(n): n < 2nBasis Step: 1 < 21(obvious)Inductive Step: If P(n) is true then P(n+1) is true for each n.• Suppose P(n): n < 2 nis true• Show P(n+1): n+1 < 2 n+1is true.n + 1 < 2 n+ 1< 2 n+ 2 n= 2 n( 1 + 1 )= 2n(2)= 2 n+14M. HauskrechtCS 441 Discrete mathematics for CSMathematical inductionExample: Prove n3- n is divisible by 3 for all positive integers.• P(n): n3- n is divisible by 3Basis Step: P(1): 13- 1 = 0 is divisible by 3 (obvious)Inductive Step: If P(n) is true then P(n+1) is true for each positive integer.• Suppose P(n): n3- n is divisible by 3 is true.• Show P(n+1): (n+1) 3- (n+1) is divisible by 3.(n+1) 3- (n+1) = n3+ 3n2+ 3n + 1 - n - 1= (n3- n) + 3n2+ 3n= (n3- n) + 3(n 2+ n)divisible by 3 divisible by 3M. HauskrechtCS 441 Discrete mathematics for CSStrong induction • The regular induction:– uses the basic step P(1) and– inductive step P(n-1)  P(n)• Strong induction uses:– Uses the basis step P(1) and– inductive step P(1) and P(2) … P(n-1)  P(n)Example: Show that a positive integer greater than 1 can be written as a product of primes.5M. HauskrechtCS 441 Discrete mathematics for CSStrong induction Example: Show that a positive integer greater than 1 can be written as a product of primes.Assume P(n): an integer n can be written as a product of primes.Basis step: P(2) is trueInductive step: Assume true for P(2),P(3), … P(n)Show that P(n+1) is true as well.2 Cases:• If n+1 is a prime then P(n+1) is trivially true• If n+1 is a composite then it can be written as a product of two integers (n+1) = a*b such that 1< a ,b < n+1 • From the assumption P(a) and P(b) holds. • Thus, n+1 can be written as a product of primes• End of proofM. HauskrechtCS 441 Discrete mathematics for CSRecursive Definitions• Sometimes it is possible to define an object (function, sequence, algorithm, structure) in terms of itself. This process is calledrecursion.Examples:• Recursive definition of an arithmetic sequence:– an= a+nd– an =an-1+d , a0= a • Recursive definition of a geometric sequence:• xn= arn• xn= rxn-1, x0 =a6M. HauskrechtCS 441 Discrete mathematics for CSRecursive Definitions• In some instances recursive definitions of objects may be much easier to writeExamples: • Algorithm for computing the gcd:• gcd(79, 35) = gcd(35, 9)• More general: gcd(a, b) = gcd(b, a mod b)• Factorial function:• n! = n (n-1)! and 0!=1M. HauskrechtCS 441 Discrete mathematics for CSRecursively Defined FunctionsTo define a function on the set of nonnegative integers• 1. Specify the value of the function at 0• 2. Give a rule for finding the function's value at n+1 in terms of the function's value at integers i  n.Example: factorial function definition• 0! = 1• n! = n (n-1)!• recursive or inductive definition of a function on nonnegative integers7M. HauskrechtCS 441 Discrete mathematics for CSRecursively defined functions Example: Assume a recursive function on positive integers:• f(0) = 3• f(n+1) = 2f(n) + 3• What is the value of f(0) ? 3 • f(1) = 2f(0) + 3 = 2(3) + 3 = 6 + 3 = 9• f(2) = f(1 + 1) = 2f(1) + 3 = 2(9) + 3 = 18 + 3 = 21• f(3) = f(2 + 1) = 2f(2) + 3 = 2(21) = 42 + 3 = 45• f(4) = f(3 + 1) = 2f(3) + 3 = 2(45) + 3 = 90 + 3 = 93M. HauskrechtCS 441 Discrete mathematics for CSRecursive definitions • Example:Define the function:f(n) = 2n + 1 n = 0, 1, 2, ... recursively.• f(0) = 1• f(n+1) = f(n) + 28M. HauskrechtCS 441 Discrete mathematics for CSRecursive definitions • Example:Define the sequence:an= n2for n = 1,2,3, ... recursively.•a1= 1•an+1= an2+ (2n + 1), n  1M. HauskrechtCS 441 Discrete mathematics for CSRecursive