4.7 Recurrence relations P13,P100 Definition: A recurrence relation for the sequencefan is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, 0, aj,..., an-1, for all integers n with neno, where no is a nonnegative integer A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation Initial condition: the information about the beginning of the sequence
4.7 Recurrence Relations ▪ P13, P100 ▪ Definition: 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 nn0 , where n0 is a nonnegative integer. ▪ A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. ▪ Initial condition: the information about the beginning of the sequence
Example(fibonacci sequence): 13世纪初意大利数学家 fibonacci研究过著名的兔 子繁殖数目问题 A young pair rabbits (one of each sex) is placed in enclosure. A pair rabbits dose not breed until they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits in the enclosure after n months, assuming that no rabbits ever die Solution: Let fn be the number of pairs of rabbits after n months ()Born during month n (2)Present in month n-1 Fn=Fn+Fn-, FI=F2=1
▪ Example(Fibonacci sequence): ▪ 13 世纪初意大利数学家 Fibonacci 研究过著名的兔 子繁殖数目问题 ▪ A young pair rabbits (one of each sex) is placed in enclosure. A pair rabbits dose not breed until they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits in the enclosure after n months, assuming that no rabbits ever die. ▪ Solution: Let Fn be the number of pairs of rabbits after n months, ▪ (1)Born during month n ▪ (2)Present in month n-1 ▪ Fn=Fn-2+Fn-1，F1=F2=1
Example(the Tower of Hanoi): There are three pegs and n circular disks of increasing size on one peg, with the largest disk on the bottom. These disks are to be transferred, one at a time, onto another of the pegs, with the provision that at no time is one allowed to place a larger disk on top of a smaller one. The problem is to determine the number of moves necessary for the transfer. Solution: Let h(n) denote the number of moves needed to solve the Tower of Hanoi problem with n disks. h(1)=1 ()We must first transfer the top n-1 disks to a peg (Then we transfer the largest disk to the vacant peg ()Lastly, we transfer the n-1 disks to the peg which contains the largest disk h(n)=2h(n-1)+1,h(1)=1
▪ Example (The Tower of Hanoi): There are three pegs and n circular disks of increasing size on one peg, with the largest disk on the bottom. These disks are to be transferred, one at a time, onto another of the pegs, with the provision that at no time is one allowed to place a larger disk on top of a smaller one. The problem is to determine the number of moves necessary for the transfer. ▪ Solution: Let h(n) denote the number of moves needed to solve the Tower of Hanoi problem with n disks. h(1)=1 ▪ (1)We must first transfer the top n-1 disks to a peg ▪ (2)Then we transfer the largest disk to the vacant peg ▪ (3)Lastly, we transfer the n-1 disks to the peg which contains the largest disk. ▪ h(n)=2h(n-1)+1, h(1)=1
Using Characteristic roots to solve recurrence relations Using generating functions to solve recurrence relations
▪ Using Characteristic roots to solve recurrence relations ▪ Using Generating functions to solve recurrence relations
4.7.1 Using Characteristic roots to solve recurrence relations Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form anhjan-th2an-+.. thkan-ks where hi are constants for all i=1,2,…,knk, and hk≠0. Definition: A linear nonhomogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an=han-th2an-2+.. thkan-k+f(n), where h; are constants for all i=1, 2,., k,n>k, and hk0
4.7.1 Using Characteristic roots to solve recurrence relations ▪ Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form ▪ an=h1an-1+h2an-2+…+hkan-k , where hi are constants for all i=1,2,…,k,n≥k, and hk≠0. ▪ Definition: A linear nonhomogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form ▪ an=h1an-1+h2an-2+…+hkan-k+f(n), where hi are constants for all i=1,2,…,k,n≥k, and hk≠0