Difference and functional equations Definition

Solution 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}$ . A solution of $E$ is a sequence $u : \mathbb{N} \to R$ such that $u_{n+d} = \sum_{i=0}^{d-1} c_i\, u_{n+i} \quad \text{for all } n \in \mathbb{N}.$

Remarks

Each choice of the initial values $u_0, \dots, u_{d-1}$ gives exactly one solution. The sum of two solutions is a solution, and a multiple of a solution is a solution. So the solutions form the space of solutions. For $u_{n+2} = u_{n+1} + u_n$ , the Lucas numbers $2, 1, 3, 4, 7, 11, \dots$ form a solution.

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
Solution of a linear recurrence definition

Where this leads

5 pages build on this one.

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

Solution of a linear recurrence

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by