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