--- title: "Recurrence Relations and Characteristic Roots" description: "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." canonical: https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB source: https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Mathematics · Area: Discrete Mathematics · Ages 19 to 20 Page: https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB ## Ready when they can - 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 ## Lesson: From a recurrence to a closed formula 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. **Example.** 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. **Example.** 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. **Example.** 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. *(drawing: The ending cases give every valid length-two string once. The string 11 is excluded.)* **Recap.** 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.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Proof by Induction and Strong Induction](https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC) ## Optional connections - [Second-Order Linear Equations with Constant Coefficients](https://lightmysky.com/learn/mathematics/second-order-linear-equations-with-constant-coefficients-mt_G7sMq1EHwQ) - [Inclusion-Exclusion](https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA) ## Opens up - [Generating Functions](https://lightmysky.com/learn/mathematics/generating-functions-mt_WAX3O-HjRk)