Difference and functional equations Definition

Space of solutions of a linear recurrence

Builds on Solution of a linear recurrence

Definition

Let $R$ be a commutative ring, and let $E$ be a linear recurrence with constant coefficients over $R$ of order $d$ . The space of solutions of $E$ is the set of all solutions of $E$ . It is a submodule of the $R$ -module $R^{\mathbb{N}}$ of all sequences in $R$ , with termwise addition and scalar multiplication.

Remarks

The map $u \mapsto (u_0, \dots, u_{d-1})$ is an isomorphism of $R$ -modules from the space of solutions to $R^d$ . Over a field, the space of solutions has dimension $d$ . For the Fibonacci recurrence over $\mathbb{R}$ , the sequences $\varphi^n$ and $\psi^n$ form a basis, with $\varphi$ and $\psi$ the roots of $X^2 - X - 1$ .

Reading path

To understand this page from the ground up, read these 4 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
Solution of a linear recurrence definition
Space of solutions of a linear recurrence definition

Where this leads

1 page builds on this one.

Dimension of the solution space of a linear recurrence

Tag	`05BDYVQQ0T`
URI	`m2://05BDYVQQ0T`
Kind	definition
Writing	W0 stub
MSC	39A06
Defines	Space of solutions of a linear recurrence
Uses	Solution of a linear recurrence

Space of solutions of a linear recurrence

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by