Recurrence Relations and Characteristic Roots
Model a counting process with a recurrence. Solve second-order homogeneous recurrences with constant coefficients, including repeated characteristic roots, and fit the constants to the initial values.
What a learner can do afterwards
- Set up a linear recurrence from a described counting process
- Determine the initial data required by a second-order homogeneous recurrence with constant coefficients, solve the recurrence and fit the constants to the initial values
- Handle a repeated characteristic root and explain why an extra factor of n appears
1 · Read
A recurrence defines terms from earlier terms. Write a0 for a(0); indexes here are nonnegative integers. A first-order rule needs one initial value. A second-order rule needs a0 and a1. For a(n)=a(n-1)+a(n-2), add the two preceding values, starting at n=2. For p(n)=2*p(n-1), double the preceding value, starting at n=1. If p0=5, three doublings reach p3=40.
For a(n)=c*a(n-1)+d*a(n-2), n>=2, c and d are constants, d nonzero. Homogeneous means no separate added term. Try a(n)=r^n with r nonzero. Use r^u/r^v=r^(u-v) to divide by r^(n-2), giving r^2-c*r-d=0. Zero is not a root since d is nonzero. For c=6, d=-8, 2+4=6 and 2*4=8, so r^2-6*r+8=(r-2)(r-4). A zero product has a zero factor: roots are 2 and 4. We study distinct and repeated real roots.
Distinct roots r1 and r2 give a(n)=A*r1^n+B*r2^n. Each root power satisfies the rule, and so does their linear combination. For a(n)=6*a(n-1)-5*a(n-2), roots are 1 and 5. With a0=3 and a1=11, use A+B=3 and A+5B=11. Subtraction gives 4B=8, so B=2 and A=1. Thus a(n)=1+2*5^n. For a negative root, keep parentheses around the base, as in (-2)^n.
A repeated nonzero root r gives a(n)=(A+B*n)*r^n. Its rule has coefficients 2*r and -r^2. Besides r^n, the sequence n*r^n satisfies it: substitution and division by r^n give 2(n-1)-(n-2)=n. These solutions are independent because their ratio is n, not a constant. Two copies of r^n combine into one constant times r^n and cannot fit arbitrary pairs of initial values.
For a(n)=8*a(n-1)-16*a(n-2), the characteristic equation is (r-4)^2=0. Use a(n)=(A+B*n)*4^n. If a0=3 and a1=16, substituting n=0 gives A=3. Substituting n=1 gives 4(A+B)=16, so A+B=4 and B=1. The fitted formula is (3+n)*4^n. For any repeated nonzero root r, the initial equations are A=a0 and r(A+B)=a1.
A supplied closed formula can be evaluated even when the recurrence is not homogeneous. Let e0=2 and e(n)=3*e(n-1)+2. The supplied formula e(n)=3*3^n-1 gives e2=3*9-1=26. Iteration agrees: e1=8 and e2=26. Substitute the requested index and calculate the power first. This evaluation does not use the homogeneous characteristic-root template to solve the rule with an added constant.
Matching several terms does not prove a formula; one mismatch rejects it. To prove a formula for a second-order recurrence, check a0 and a1 and show that the formula satisfies the rule for every n>=2. Induction then carries agreement forward: if the two preceding terms agree, the rule makes the next terms agree. A formula that matches both initial values but disagrees at n=2 does not describe the sequence.
A bit is 0 or 1. Let b(n) count strings of n bits with no adjacent 1s. For n>=2, strings ending in 0 come from valid length n-1 strings. Strings ending in 1 must end in 01 and come from valid length n-2 strings. Removing and appending these endings are inverse operations. The cases do not overlap, so b(n)=b(n-1)+b(n-2). The empty string gives b0=1; strings 0 and 1 give b1=2.
State the rule and initial values. For a homogeneous constant-coefficient rule, solve for the roots and fit the constants. Prove the formula using its initial values and the recurrence identity.
The lesson, questions and flashcards were written for this dataset.
The questions, readings and flashcards were written for this dataset. The linked videos are Khan Academy resources. No license grant for the videos is asserted.
More to read
Counting by the final bit
Let b(n) count length-n strings made from 0s and 1s with no adjacent 1s. Start with b0=1 for the empty string and b1=2 for the strings 0 and 1.
For n>=2, a valid string ends in either 0 or 1. Removing a final 0 leaves any valid string of length n-1. A final 1 must follow a 0. Removing that ending 01 leaves any valid string of length n-2. Appending the removed ending reverses each operation.
These cases cover all valid strings and have no overlap. Therefore b(n)=b(n-1)+b(n-2). At length two, the strings are 00, 10 and 01. This agrees with b2=b1+b0=3. The counting argument explains the recurrence; the initial values let it run.
A formula with a negative characteristic root
Consider a(n)=3*a(n-1)+10*a(n-2) for n>=2. Substituting r^n gives r^2-3*r-10=0. Factoring as (r-5)(r+2) identifies roots 5 and -2. The general solution is a(n)=A*5^n+B*(-2)^n.
Suppose a0=2 and a1=17. The initial equations are A+B=2 and 5A-2B=17. Add twice the first equation to the second: 7A=21. Hence A=3 and B=-1. The formula is a(n)=3*5^n-(-2)^n.
At n=2 it gives 75-4=71. The recurrence also gives 3*17+10*2=71. Parentheses matter: (-2)^2 is 4, while (-2)^3 is -8. This term check can catch an arithmetic slip. To establish the formula at all indexes, check both initial values and verify that its root powers satisfy the recurrence.
Two independent solutions from one repeated root
For a(n)=10*a(n-1)-25*a(n-2), the characteristic polynomial is (r-5)^2. Two copies of 5^n collapse: A*5^n+B*5^n=(A+B)*5^n. Only the sum of the constants changes the sequence.
The sequence n*5^n also satisfies this recurrence. Substitute it on the right and divide by 5^n. The result is 2(n-1)-(n-2)=n, as required. Its ratio to 5^n is n, so neither sequence is a constant multiple of the other.
Use a(n)=(A+B*n)*5^n. If a0=1 and a1=15, then A=1 and 5(A+B)=15. Thus B=2, giving a(n)=(1+2*n)*5^n. At index two the formula gives 125, and the recurrence gives 10*15-25*1=125. The recurrence identity, together with the initial values, establishes agreement beyond this one check.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.