Characteristic Equation Method

Combinatorics · Axiom Academy

LESSON Characteristic Equation Method Learn how to solve linear recurrence relations by finding roots of the characteristic equation 1. From Recurrence to Characteristic Equation Consider the recurrence relation a n = 5a n-1 - 6a n-2 with initial conditions a 0 = 1, a 1 = 2. Key idea: Assume a solution of the form a n = r n for some constant r. Substitute this into the recurrence relation. The characteristic equation r 2 - 5r + 6 = 0 is a quadratic equation. We can solve it by factoring or using the quadratic formula. Factoring approach: Look for two numbers that multiply to 6 and add to -5. 3. Building the General Solution When we have distinct roots r 1 and r 2 , the general solution is a linear combination: General form: a n = c 1 · r 1 n + c 2 · r 2 n Use the initial conditions a 0 = 1 and a 1 = 2 to find the constants c 1 and c 2 .

This is the written version of the interactive lesson above. See the full Combinatorics course.