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 solutions
Substitute . 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 .

Ancestors (5)

  1. Linear recurrence relation
  2. Algebra
  3. Area of mathematics
  4. Mathematics
  5. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.