Difference and functional equations Linear difference equations Theorem

Geometric solutions come from roots of the characteristic polynomial

Builds on Solution of a linear recurrence Characteristic polynomial of a linear recurrence

Statement

Let $R$ be a commutative ring, let $E$ be a linear recurrence with constant coefficients over $R$ , and let $q \in R$ . Then the sequence $(q^n)_{n \ge 0}$ is a solution of $E$ if and only if $q$ is a root of the characteristic polynomial $\chi_E$ .

Remarks

Proof idea: for the sequence $q^n$ the recurrence at index $n$ reads $q^n \chi_E(q) = 0$ . At $n = 0$ this is $\chi_E(q) = 0$ . Over a field, if $\chi_E$ has $d$ distinct roots $q_1, \dots, q_d$ , every solution is $u_n = a_1 q_1^n + \dots + a_d q_d^n$ with constants $a_i$ . Binet's formula is the case of the Fibonacci recurrence.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Recurrence relation definition
Linear recurrence with constant coefficients definition
Characteristic polynomial of a linear recurrence definition
Solution of a linear recurrence definition
Geometric solutions come from roots of the characteristic polynomial statement

Tag	`096SD4ERQH`
URI	`m2://096SD4ERQH`
Kind	statement, theorem
Writing	W0 stub
MSC	39A06
Status	This copy of the site has no build data. Run `m2 status 096SD4ERQH`.
Uses	Solution of a linear recurrence, Characteristic polynomial of a linear recurrence

Geometric solutions come from roots of the characteristic polynomial

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here