CSE115/ENGR160 Discrete Mathematics 04/19/128.1 Recurrence relationsRecurrence relationsRecursion and recurrenceExampleSlide 6Modeling with recurrence relationsSlide 8Slide 98.2 Solving linear recurrence relationsFrom mathematical inductionLinear homogenous recurrence relations with constant coefficientsTheorem 1Slide 14Fibonacci numbersProof: α_1 〖r_1^ 〗^n+α_2 〖r_2^ 〗^n→ c_1 a_(n-1)+c_2 a_(n-2)Proof: 〖c_1 a_(n-1)+c_2 a_(n-2)→α〗_1 〖r_1^ 〗^n+α_2 〖r_2^ 〗^nSlide 188.5 Inclusion-exclusionPrinciple of inclusion-exclusionSlide 21Slide 22Slide 23Slide 24CSE115/ENGR160 Discrete Mathematics04/19/12Ming-Hsuan YangUC Merced18.1 Recurrence relations•Many counting problems can be solved with recurrence relations•Example: The number of bacteria doubles every 2 hours. If a colony begins with 5 bacteria, how many will be present in n hours?•Let an=2an-1 where n is a positive integer with a0=52Recurrence relations•A recurrence relation for the sequence {an} is an equation that expresses an in terms of 1 or more of the previous terms of the sequence, i.e., a0, a1, …, an-1, for all integers n with n≥n0 where n0 is a nonnegative integer•A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation3Recursion and recurrence•A recursive algorithm provides the solution of a problem of size n in terms of the solutions of one or more instances of the same problem of smaller size•When we analyze the complexity of a recursive algorithm, we obtain a recurrence relation that expresses the number of operations required to solve a problem of size n in terms of the number of operations required to solve the problem for one or more instance of smaller size4Example•Let {an} be a sequence that satisfies the recurrence relation an=an-1 – an-2 for n=2, 3, 4, … and suppose that a0=3 and a1=5, what are a2 and a3?•Using the recurrence relation, a2=a1-a0=5-3=2 and a3=a2-a1=2-5=-35Example•Determine whether the sequence {an}, where an=3n for every nonnegative integer n, is a solution of the recurrence relation an=2an-1 – an-2 for n=2, 3, 4, …•Suppose an=3n for every nonnegative integer n. Then for n≥2, we have 2an-1-an-2=2(3(n-1))-3(n-2)=3n=an. •Thus, {an} where an=3n is a solution for the recurrence relation6Modeling with recurrence relations•Compound interest: Suppose that a person deposits $10,000 in a savings account at a bank yielding 11% per year with interest compounded annually. How much will it be in the account after 30 years?•Let Pn denote the amount in the account after n years. The amount after n years equals the amount in the amount after n-1 years plus interest for the n-th year, we see the sequence {Pn} has the recurrence relation Pn=Pn-1+0.11Pn-1=(1.11)Pn-17Modeling with recurrence relations•The initial condition P0=10,000, thus•P1=(1.11)P0•P2=(1.11)P1=(1.11)2P0•P3=(1.11)P2=(1.11)3P0•…•Pn=(1.11)Pn-1=(1.11)nP0•We can use mathematical induction to establish its validity8Modeling with recurrence relations•We can use mathematical induction to establish its validity•Assume Pn=(1.11)n10,000. Then from the recurrence relation and the induction hypothesis •Pn+1=(1.11)Pn=(1.11)(1.11)n10,000=(1.11)n+110,000•n=30, P30=(1.11)3010,000=228,922.9798.2 Solving linear recurrence relations10From mathematical induction11Linear homogenous recurrence relations with constant coefficients12characteristic equationTheorem 113Example14Fibonacci numbers151617Recurrence relations•Play an important role in many aspects of algorithms and complexity•Can be used to –analyze the complexity of divide-and-conquer algorithms (e.g., merge sort)–Solve dynamic programming problems (e.g., scheduling tasks, shortest-path, hidden Markov model)–Fractal 188.5 Inclusion-exclusion•The principle of inclusion-exclusion: For two sets A and B, the number of elements in the union is defined by |A⋃B|=|A|+|B|-|A⋂B|•Example: How many positive integers not exceeding 1000 are divisible by 7 or 11? 192201290142117100011100071000|||||||| BABABA Principle of inclusion-exclusion•Consider union of n sets, where n is a positive integer•Let n=320|||||||||||||||| CBAACCBBACBACBA  Principle of inclusion-exclusion•Let A1, A2, …, An be finite sets. Then•Proof: Prove it by showing that an element in the union is counted exactly once by the right-hand side of the equation•Suppose that a is a member of exactly r of the sets A1, A2, …, An where 1≤r≤n•This element is counted C(r,1) times by ∑|Ai|21||)1(||||||||211,,1,1121nnnkjikjinjijiniinAAAAAAAAAAAAPrinciple of inclusion-exclusion•It is counted C(r,2) times by ∑|Ai⋂ Aj | •In general, it is counted C(r,m) times by the summation involving m of the sets Ai. Thus, this element is counted exactly C(r,1)-C(r,2)+C(r,3)-…+(-1)r+1C(r,r)•Recall , C(r,0)-C(r,1)+C(r,2)-C(r,3)-…+(-1)rC(r,r)=0•Thus, C(r,1)-C(r,2)+C(r,3)-…+(-1)r+1C(r,r)=C(r,0)=1•Thus, this element a is counted exactly once by the right hand side22nkkkn00)1(Principle of inclusion-exclusion•Gives a formula for the number of elements in the union of n sets for every positive integer n•There are terms in this formula for the number of elements in the intersection of every nonempty subset of the collection of the n sets. Hence there are 2n-1 terms in the formula•Example: 15 terms 23||||||||||||||||||||||||||||||||432143243142132143423241312143214321AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAExample•For the union of 4 sets, there are 15 different terms, one for each nonempty subset of {A1, A2, A3,