Recurrence RelationsDefinitionRecurrence Relations vs. Recursive DefinitionsExampleSlide 5Modeling with Recurrence RelationsRabbits and the Fibonacci SequenceThe Tower of HanoiMore ExampleExercisesCSE 2813 Discrete StructuresRecurrence RelationsSection 6.1CSE 2813 Discrete StructuresDefinition•A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, 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 relation.CSE 2813 Discrete StructuresRecurrence Relations vs. Recursive Definitions•So what is the difference?•Recursive definitions can be used to solve counting problems. When they are used in this way, the rule for finding terms from those that precede them is called a recurrence relation.CSE 2813 Discrete StructuresExample•Let {an} be a sequence that satisfies the recurrence relation an = an-1 an-2 for n = 2, 3, 4,… Suppose that a0 = 3 and a1 = 5.•What are a2 and a3?CSE 2813 Discrete StructuresExample•Consider the recurrence relation: an = 2an-1 an-2 for n = 2, 3, 4, …•Show whether each of the following is a solution of this recurrence relation? an = 3n an = 2n an = 5CSE 2813 Discrete StructuresModeling with Recurrence Relations•A person deposits $10,000 in a savings account at a bank yielding 11% per year with interest compounded annually.•How much will be in the account after 30 years?CSE 2813 Discrete StructuresRabbits and theFibonacci Sequence•A young pair of rabbits (one of each sex) is placed on an island.–A pair does not breed until they are 2 months old.–After they are 2 months old, each pair produces another pair each month.•Find the number of pairs of rabbits on the island after n months, assuming that no rabbits ever die.CSE 2813 Discrete StructuresThe Tower of Hanoi•Find a recurrence relation to find the number of moves needed to solve the Tower of Hanoi problem with n disks.Tower of HanoiCSE 2813 Discrete StructuresMore Example•Find a recurrence relation for the number of bit strings of length n that do not contain two consecutive 0s.•Find a recurrence relation for the number of bit strings of length n that contain two consecutive 0s.CSE 2813 Discrete StructuresExercises•1, 5, 9, 10, 11, 13, 24, 25,
View Full Document
Unlocking...