Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 171Induction and Recursion. Explicit definitionRecursive definition12)...1(! nnn1 if)!1(0 if1!nnnnnnnqqqS ...120 if0 if11nqSnSnnnRRRRn ...1 if1 if1nRRnRRnn• Factorial• Geometric progression • Power of relation on a set2• 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.3How 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• Quadratic function of integer n: g2(n) = an2+bn+cg2(n+1) = a(n+1)2+b(n+1)+c = g2(n) +2an+(a+b)0 if)1(0 if)(11nangnbng0 if)(2)1(0 if)(22nbaanngncng4Example. Prove that for all positive integers m and n, nmmnRRR Proof. Let m be arbitrary positive integer and then prove by induction on n1.1) Basis. n=1: (by recursive definition of Rm+1) 11RRRmm2) IH: Assume that for some k 1 we have IS: We need to prove that kmkmRRR )1()1( kmkmRRR 1)()1(RRRkmkmRRRkm )(…..by IH )( RRRkm….association of composition1kmRR ……..definition of composition ……..definition of composition5Theorem. The transitive closure of R isTransitive closures again....32ZRRRRnnProof. Denote . We need to prove that S satisfies thedefinition of transitive closure, i. e.i) S includes R, R S ii) S is transitiveiii) S is the smallest relation satisfying i) and ii).nnRSZii) 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, nZ+.(y, z ) S implies that (y, z ) Rm, m is some integer , nZ+.(x, z) Rno Rm= Rn+m, by the previous Theorem. (x, z) S , since Rn+mS6iii) Suppose T is any relation, satisfying i) RT and ii) T is transitive. and prove that S T .By the definition of S as , it suffices to prove that for any nZ+ (Rn T) We are going to prove it by induction on n 1.nnRSZ1) Basis: when n=1, R1=RT 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 RT 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.7 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 (n1), plus offspring pairs for all pairs from month (n2), i. e. :Fibonacci Numbers21 nnnFFF, n 281 if1 if10 if021nFFnnFnnnProof by induction on n 0.120000FFFii?1) Basis. Take n=0 and check that 101012 FFFBy the recurrent formula for n =2 we have so F21=0 and F0=0.So, Fibonacci numbers can be defined recursively: These numbers have numerous applications in CS, mathematics, theory of games.120nniiFFLet’s prove the closed formula for the sum for all integers n 092) IH: Assume that the summation formula is correct for n=k, where k is some integer k 0, i. e. 120kkiiFFIS: We need to prove that 12)1(10kkiiFF11010...kkkiiFFFFF10kkiiFF121kkFF…………by IH 11321 kkkFFF……..by recurrence formula for (k+3) >110• Sometimes we need stronger assumption to prove IS. Strong Induction Principle: Let AN denote a subset that satisfies the following two properties: 1) 0A;2) if 0, 1, …kA, then k+1A.Then A=N.So, Strong Induction differs from Induction Principle in step 2): IP2) n 0 [P (n) P (n+1)]Strong Induction 2) n 0 [(m n P (m)) P (n+1)]• It happens when to prove IS for (n +1) you need to refer not only to the previous n , but to smaller numbers.11Example. Prove that every amount of postage of 12 cents or morecan 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. 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) As we proceed n n +1, we can not derive case n +1 from thecase n nn +1(n+1)4(n+1)5We need to prove an extended basis here, that is to provethe basis on more then one point.12Proof.1) Basis (extended): check that we can form postage of 12, 13, 14, and 15 cents using only 4c and 5c stamps.12=43; 13=5+ 42; 14=5 2+4; 15=53.2) IH: Assume that any postage 12, … k, where k 15 can be made using 4c and 5c stamps (strong induction) IS Prove that conjecture is true for the postage k +1. By IH any postage greater or equal then 12c and less or equal kcan be formed using 4c and 5c stamps. In particular it is true for k 3. Together with one more 4c stamp it gives k +1 postage.13Theorem. The following three principles are equivalent: (a) the Induction Principle; (b) the Strong Induction Principle; and (c) the Well-Ordering principle. Proof. It suffices to prove (a)(b), (b)(c), and (c)(a). We already did this14Proof of (a)(b): Let AN and A satisfies the two properties: (1)
View Full Document
Unlocking...