For a constant-coefficient linear recurrence relation, substituting a trial sequence produces a polynomial equation in called its characteristic equation. Repeated roots contribute factors polynomial in .
For a constant-coefficient linear recurrence relation over the complex numbers, a nonzero root of multiplicity in its characteristic polynomial of a linear recurrence supplies the linearly independent solutionsSubstitute . Each factor of the shift linear operator becomes times the forward difference operator on , so its th power kills every polynomial in of degree less than . Their independence follows from the Lagrange root bound over a field. The same argument works over a field of characteristic zero; the displayed monomials need modification in positive characteristic.
A zero root needs separate initial-data treatment: for characteristic polynomial , the recurrence relation is , leaving the first values arbitrary.
For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots , the solution is . If , boundedness for forces , and fixes . This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor .
Articles by others on the same topic
There are currently no matching articles.