Discrete math Exercise et go F a q1 and qn 1 qm1qn2 Assuming

Discrete math

Exercise et go F a, q1 and qn (1 qm-1)/qn-2. Assuming that an 0 for all n L solve this recurrence relation. Hint: q4 1 a)/B

Solution

Let q be a root with multiplicity m of the characteristic equation (9) associated with the kth order homogeneous linear recurrence relation (8) with constant coefficients. Then the m sequences xn = q n , nqn , . . . , nm1 q n are linearly independent solutions of the recurrence relation (8). (b) Let q1, q2, . . . , qs be distinct roots with the multiplicities m1, m2, . . . , ms respectively for the characteristic equation (9). Then the sequences xn = q n 1 , nqn 1 , . . . , nm11 q n 1 ; q n 2 , nqn 2 , . . . , nm21 q n 2 ; . . . q n s , nqn s , . . . , nms1 q n s ; n 0

are linearly independent solutions of the homogeneous linear recurrence relation (8). Their linear combinations form the general solution of the recurrence relation.