Induction and Recursion Recursive definition Explicit definition Factorial n n n 1 2 1 Geometric progression S n 1 q q 2 q n Power of relation on a set if n 0 1 n n n 1 if n 1 1 S n n S q n 1 if n 0 if n 0 if n 1 R R n 1 R R if n 1 n R n R R R 1 The recursive definition of a function makes reference to earlier versions of itself The main connection between recursion and induction is that objects are defined by means of a natural sequence Induction is usually the best possibly the only way to prove results about recursively defined objects 2 How to find a closed form for a recursively defined function In general there is no ready to use recipe Some simple cases are Linear function of integer n g1 n an b g1 n 1 a n 1 b g1 n a if n 0 b g1 n g1 n 1 a if n 0 Quadratic function of integer n g2 n an2 bn c g2 n 1 a n 1 2 b n 1 c g2 n 2an a b if n 0 c g 2 n g 2 n 1 2an a b if n 0 3 n m R m R n Example Prove that for all positive integers m and n R Proof Let m be arbitrary positive integer and then prove by induction on n 1 1 Basis n 1 1 recursive definition of Rm 1 R m 1 R m R by m k R m R k 2 IH Assume that for some k 1 we have R m k 1 R m R k 1 IS We need to prove that R R m k 1 R m k R1 definition of composition R m R k R by IH R m R k R association of composition R m R k 1 definition of composition 4 Transitive closures again Theorem The transitive closure of R is R n R R 2 R 3 n n Z Proof Denote S R We need to prove that S satisfies the n Z definition of transitive closure i e i S includes R R S ii S is transitive iii S is the smallest relation satisfying i and ii ii assume x y S and y z S to prove that x z S x y S implies that x y Rn n is some integer n Z y z S implies that y z Rm m is some integer n Z x z Rno Rm Rn m by the previous Theorem x z S since Rn m S 5 iii Suppose T is any relation satisfying i R T and ii T is transitive and prove that S T By the definition of S as S R n it suffices to prove n Z that for any n Z Rn T We are going to prove it by induction on n 1 1 Basis when n 1 R1 R T by assumption 2 IH Assume that for n k where k is some integer k 1 Rk T IS Need to prove Rk 1 T Suppose x y Rk 1 Rko R by definition of composition It implies that there exists some z A that x z Rk and z y R x z Rk implies x z T because Rk T by IH z y R implies z y T because R T by assumption x z T and z y T imply x y T by transitive property of T We proved by induction that for any n 1 Rn T 6 Fibonacci Numbers The sequence named for Fibonacci 1202 is introduced in terms of rabbits Suppose that every month a breeding pair of rabbits produce a pair of offspring The offspring in turn start breeding two months later and so on Denote Fn the number of pairs in month n Suppose you buy a pair of rabbits in month 1 F0 0 F1 1 then you still have one pair in month 2 F2 1 but in month 3 they start breeding F3 2 The sequence begins 0 1 1 2 3 5 8 13 21 You can observe that in a month n you have all pairs from the previous month n 1 plus offspring pairs for all pairs from month n 2 i e Fn Fn 1 Fn 2 n 2 7 So Fibonacci numbers can be defined recursively 0 Fn 1 F F n 2 n 1 if n 0 if n 1 if n 1 These numbers have numerous applications in CS mathematics theory of games n Let s prove the closed formula for the sum Fi Fn 2 1 i 0 for all integers n 0 Proof by induction on n 0 1 Basis Take n 0 and check that 0 F i i 0 F0 F0 2 1 By the recurrent formula for n 2 we have F2 F1 F0 1 0 1 so F2 1 0 and F0 0 8 2 IH Assume that the summation formula is correct for n k where k is some integer k 0 i e k F F i i 0 k 2 1 IS We need to prove that k 1 F F i i 0 0 k 1 F F i i 0 k 1 2 1 F1 Fk Fk 1 k Fi Fk 1 i 0 Fk 2 1 Fk 1 by IH Fk 1 Fk 2 1 Fk 3 1 by recurrence formula for k 3 1 9 Sometimes we need stronger assumption to prove IS It happens when to prove IS for n 1 you need to refer not only to the previous n but to smaller numbers Strong Induction Principle Let A N denote a subset that satisfies the following two properties 1 0 A 2 if 0 1 k A then k 1 A Then A N So Strong Induction differs from Induction Principle in step 2 IP 2 n 0 P n P n 1 Strong Induction 2 n 0 m n P m P n 1 10 Example Prove that every amount of postage of 12 cents or more can be formed using only 4 cent and 5 cent stamps We are going to prove by induction on n 12 that any postage n 5i 4j where integers i j 0 As we proceed n n 1 we can not derive case n 1 from the case n n 1 5 n 1 4 n n 1 We can infer n 1 5i 4j either from n 1 5 5 i 1 4j or from n 1 4 5i 4 j 1 We need to prove an extended basis here that is to prove the basis on more then one point 11 Proof 1 Basis extended check that we can form postage of 12 13 14 and 15 cents using only 4c and 5c stamps 12 4 3 13 5 4 2 14 5 2 4 15 5 3 2 IH Assume that any postage …
View Full Document
Unlocking...