V Adamchik 21 127 Concepts of Mathematics Mathematical Induction Victor Adamchik Fall of 2005 Lecture 3 out of three Plan 1 Recursive Definitions 2 Recursively Defined Sets 3 Program Correctness Recursive Definitions Sometimes it is easier to define an object using a self reference For example A linked list is either empty list or a node followed by a linked list A binary tree is either empty tree or a node containing left and right binary trees Sometimes self referencing leads to paradoxes The set of all sets which aren t elements of themselves The process of defining an object using a self reference is called recursion A primitive recursion is a restricted way of defining f n 1 in terms of f n A recursive function is a function that calls itself in order to return an answer A recursive definition of a function is given in two parts 1 a set of base values or initial values 2 a rule for calculating f n in terms of previous values V Adamchik 21 127 Concepts of Mathematics This is a typical example of recursive definition or inductive definition f 0 f n 1 5 f n 1 Here is another example GCD 0 b GCD a b GCD a b b GCD b a if a b GCD b mod a a A palindrome is an expression that reads the same backwards and forwards For example Rats live on no evil star Madam I m Adam Let us define a palindrome over a b c d alphabet recursively Initial values P0 P1 a b c d General rule Pn a a b b c c d d 1 Pn 1 n Recursively Defined Sets We start with an example 2 if a S S b S a b S Claim The above set is a set of positive even integers Proof Let E be a set of ALL positive even integers We have to prove 1 V Adamchik 21 127 Concepts of Mathematics 1 E S 2 S E Prove 1 We need to prove that EVERY even positive integer belongs to S The proof is by induction Let P n 2n S It s easy to see that the basis step holds P 1 2 S Assume that P n is true What can we say about P n Pn since 2 n S and 2 1 2 n 1 1 2n 2 S S Prove 2 We need to prove S E namely that any element in S is divisible by 2 We use the recursive definition of S S if a Let us choose any element x x b S a b S S By the above rule a b a1 b1 a2 b2 We continue splitting until we get 2 which means that x is divivible by 2 Hence S E x 2 2 Set of Strings Given an alphabet We define a set 1 empty string 2 x if and x of all strings over this alphabet V Adamchik 21 127 Concepts of Mathematics The second rule says that new strings are generated by concatenation The length of a string L is defined by 1 L empty 2 L x 0 L 1 x Based on the above two definition we prove L Proof by induction on Basis step 1 L 2 L 1 2 1 2 2 empty By the definition of the length of a string 2 L L 1 L 1 L 2 2 1 L 1 0 1 Inductive step we assume that L for all 1 L 2 1 L 2 L 1 2 2 n We have to prove the above formula for L n 2 1 Note that by recursive definition 2 x x Therefore L 1 2 L 1 which concludes the proof x L 1 1 by I H L 1 L 1 L 1 L x V Adamchik 21 127 Concepts of Mathematics Program Correctness How can we be sure that a particular algorithm implementation is correct int prod 1 for int k 1 k n k prod k return prod The idea is to use a loop invariant an assertion that is true before and after each execution of the body of the loop precondition while guard loop body postcondition In the above example a loop invariant is the following proposition P prod k 1 k n A loop invariant should serve two purposes to state what the loop is supposed to accomplish and to help in proving the algorithm correctness To prove that P is a loop invariant we use a mathematical induction First we note that P is true before the loop is entered since prod namely after n k n 1 loop executions In the next execution k is incremented by 1 thus it becomes n and prod k 1 Next we assume that P is true for 1 k Since by inductive hypothesis the previous value of prod is 1 we conclude that prod n Therefore P remains true Finally we need to show that the program terminates which is trivial in our case V Adamchik 21 127 Concepts of Mathematics Fast Exponentiation The following program computes an where n is nonnegative integer n int x a y n z 1 while y 0 if y 2 0 x x y y 2 else y 1 z x return z Note often the hardest part of a loop invariant proof is identifying the invariant We introduce the following proposition z xy P an y and prove by induction that it is a loop invariant Basis step P is true before the loop starts because x z xy 1 a y n and z 1 an Inductive step We assume that P is true after some iterations We must show that P remains true after the next pass Let variables with hats x y z be the values after the loop body was computed Therefore we have to prove z xy an y is true We consider two cases 1 y is even After the execution of the loop body we have x2 y x z xy z x2 y 2 z y2 z xy z by I H 1 y is odd After the execution of the loop body we have an V Adamchik 21 127 Concepts of Mathematics x x y z xy y z x xy 1 z 1 z x z xy by I H Note in this case we decrement y by one Is it true that y condition is y an 0 Yes it is because the loop 0 Finally we must prove that the above program terminates It follows from the fact that the loop invariant is true when the loop terminates and the loop condition is false z xy This means that y returns z 0 and z x0 an y y 0 an So we prove that the algorithm terminates and z an Fibonacci Numbers The following program computes n th Fibonacci number n int prev 1 cur 1 if n 0 n 1 return n if n 2 return 1 for int k 3 k n k int tmp cur …