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
Definition: The equation Xk-hixk-I-h,xk-2-.-h=0 is called the characteristic equation of the recurrence relation an h an-th2an-2+.+hgan-k The solutions 91, 92,., qk of this equation are called the characteristic root of the recurrence relation where qili=1, 2, ., k is complex number. Theorem 4.18: Suppose that the characteristic equation has k distinct roots q1, 2, ., k. Then the general solution of the recurrence relation is an=C1qn+C2q2+…+ CKqk, where c1p2C2y… Ck are constants
▪ Definition: The equation xk -h1x k-1 -h2x k-2 -…-hk=0 is called the characteristic equation of the recurrence relation an=h1an-1+h2an-2+…+hkan-k . The solutions q1 ,q2 ,…,qk of this equation are called the characteristic root of the recurrence relation, where qi (i=1,2,…,k) is complex number. ▪ Theorem 4.18: Suppose that the characteristic equation has k distinct roots q1 ,q2 ,…,qk . Then the general solution of the recurrence relation is ▪ an=c1q1 n+c2q2 n+…+ckqk n , where c1 ,c2 ,…ck are constants
√3 5√3+ ence relation ch 5656 √3 6√3 √3 5√3+1 (1+√3)”+ 6√3 x2-2x-2=0 roots q1=1+31/2 q2=1-312 the general solution of the recurrence relation is an=C1(1+312)+c2(1-312), We want to determine c and c so that the initial values c1(1+312)+c2(1-312)=3, c1(1+312)2+c2(1-3122=8
▪ Example: Solve the recurrence relation ▪ an=2an-1+2an-2，(n≥2) ▪ subject to the initial values a1=3 and a2=8. ▪ characteristic equation : ▪ x 2 -2x-2=0, ▪ roots: ▪ q1=1+31/2 ，q2=1-3 1/2 。 ▪ the general solution of the recurrence relation is ▪ an=c1 (1+31/2) n+c2 (1-3 1/2) n , ▪ We want to determine c1 and c2 so that the initial values ▪ c1 (1+31/2)+c2 (1-3 1/2)=3, ▪ c1 (1+31/2) 2+c2 (1-3 1/2) 2=8 6 3 5 3 1 6 3 5 3 1 1 2 + = − c = c n n an (1 3) 6 3 5 3 1 (1 3) 6 3 5 3 1 − + + + − =
Theorem 4.19: Suppose that the characteristic equation has t distinct roots q1 25.9t with multiplicities m1, m2,...,m, respectively, So that m;2l for i=1, 2, . t and m+m,+.+m=k Then the general solution of the recurrence relation is an=∑∑cn1q where c are constants for1≤j≤m; and Isi<t
▪ Theorem 4.19: Suppose that the characteristic equation has t distinct roots q1 ,q2 ,…,qt with multiplicities m1 ,m2 ,…,mt , respectively, so that mi≥1 for i=1,2,…,t and m1+m2+…+mt=k. Then the general solution of the recurrence relation is = = − = t i m j n i j n ij i a c n q 1 1 1 where cij are constants for 1≤j≤mi and 1≤i≤t
Example: Solve the recurrence relation antan-1 3an-2-5an-3-2an-4=0, n24 subject to the initial values ao=l, a a2=0, and a3=2. characteristic equation +x3-3x2-5x-2=0 roots:-1,-1,-1,2 By Theorem 4.19: the general solution of the recurrence relation is an=c1(-1)c12n(-1)叶c13n2(-1)吗c212n We want to determine ca so that the initial values C1+C1=1 -C1-C12-C13+C21 C1+2c12+4c13+4c21=0 C1n-3c12-9c13+8c2=2 c1=7/9,c12=-13/16,c13=1/16,c21=1/8 an=7/9(-1)(13/16n(-1)+(1/16)n2(-1)+(1/8)2n
▪ Example: Solve the recurrence relation ▪ an+an-1 -3an-2 -5an-3 -2an-4=0,n≥4 ▪ subject to the initial values a0=1,a1=a2=0, and a3=2. ▪ characteristic equation ▪ x 4+x3 -3x2 -5x-2=0, ▪ roots:-1,-1,-1,2 ▪ By Theorem 4.19：the general solution of the recurrence relation is ▪ an=c11(-1)n+c12n(-1)n+c13n 2 (-1)n+c212 n ▪ We want to determine cij so that the initial values ▪ c11+c21=1 ▪ -c11-c12-c13+c21=0 ▪ c11+2c12+4c13+4c21=0 ▪ -c11-3c12-9c13+8c21=2 ▪ c11=7/9,c12=-13/16,c13=1/16,c21=1/8 ▪ an=7/9(-1)n -(13/16)n(-1)n+(1/16)n2 (-1)n+(1/8)2n
the general solution of the linear nonhomogeneous recurrence relation of degree k with constant coefficients is a=a+a a'n is the general solution of the linear homogeneous recurrence relation of degree k with constant coefficients an h an-th2an-2+.. thkan-k a is a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients an=h an-th2an-2+. thank+f(n)
▪ the general solution of the linear nonhomogeneous recurrence relation of degree k with constant coefficients is ▪ an=a'n+a n * ▪ a'n is the general solution of the linear homogeneous recurrence relation of degree k with constant coefficients an=h1an-1+h2an-2+…+hkan-k ▪ a n * is a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients ▪ an=h1an-1+h2an-2+…+hkan-k+f(n)