Difference and functional equations Definition

Characteristic polynomial of a linear recurrence

Builds on Linear recurrence with constant coefficients

Definition

Let $R$ be a commutative ring, and let $E$ be a linear recurrence with constant coefficients over $R$ , of order $d$ with coefficients $c_0, \dots, c_{d-1}$ . The characteristic polynomial of $E$ is the polynomial $\chi_E(X) = X^d - \sum_{i=0}^{d-1} c_i X^i \in R[X].$

Remarks

For the Fibonacci recurrence $u_{n+2} = u_{n+1} + u_n$ , the characteristic polynomial is $X^2 - X - 1$ . Its roots are the golden ratio $\varphi$ and $1 - \varphi$ . A geometric sequence $q^n$ is a solution if and only if $q$ is a root of $\chi_E$ . The node geometric solutions states this.

Reading path

To understand this page from the ground up, read these 3 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

Where this leads

1 page builds on this one.

Geometric solutions come from roots of the characteristic polynomial

Tag	`0BWDJGQYST`
URI	`m2://0BWDJGQYST`
Kind	definition
Writing	W0 stub
MSC	39A06
Defines	Characteristic polynomial of a linear recurrence
Uses	Linear recurrence with constant coefficients

Characteristic polynomial of a linear recurrence

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by