Linear Homogeneous Recurrences

Combinatorics · Axiom Academy

LESSON Linear Homogeneous Recurrences Learn to solve recurrence relations using the characteristic equation method A linear homogeneous recurrence relation with constant coefficients has the form: where c₁, c₂, ..., cₖ are constants with cₖ ≠ 0 . Linear: Each term is a linear combination of previous terms Homogeneous: No additional constant term (right side = 0) Constant coefficients: The multipliers c₁, c₂, ... don't depend on n Order k: Depends on the k previous terms 2. The Characteristic Equation To solve a linear homogeneous recurrence, we assume a solution of the form aₙ = rⁿ for some constant r . Substituting this into the recurrence relation gives us the characteristic equation : If aₙ = rⁿ, then aₙ₋₁ = rⁿ⁻¹, aₙ₋₂ = rⁿ⁻², etc. Substituting: rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻² + ... + cₖrⁿ⁻ᵏ Dividing by rⁿ⁻ᵏ: rᵏ = c₁rᵏ⁻¹ + c₂rᵏ⁻² + ... + cₖ 3. Finding the General Solution Once we solve the characteristic equation and find roots r₁, r₂, ..., rₖ, we can write the general solution. If all k roots are distinct, the general solution is: The constants α₁, α₂, ..., αₖ are determined by initial conditions. Using initial conditions F₀ = 0 and F₁ = 1, we can solve for α₁ and α₂. Here's the complete process for solving a linear homogeneous recurrence relation: Write the characteristic equation from the recurrence relation Solve the characteristic equation to find roots r₁, r₂, ..., rₖ Form the general solution based on the roots: Distinct roots: aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ

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