Difference and functional equations Definition

Linear recurrence with polynomial coefficients

Builds on Recurrence relation Polynomial ring

Definition

Let $K$ be a field and let $r \ge 0$ be an integer. Let $p_0, \dots, p_r \in K[n]$ be polynomials in the polynomial ring over $K$ , with $p_r \ne 0$ . The linear recurrence with polynomial coefficients $p_0, \dots, p_r$ is the recurrence relation $p_r(n)\, u_{n+r} + p_{r-1}(n)\, u_{n+r-1} + \cdots + p_0(n)\, u_n = 0 \qquad (n \in \N)$ for a sequence $u \colon \N \to K$ . Its order is $r$ , when $p_0 \ne 0$ .

Remarks

Example: the Catalan numbers $C_n$ satisfy $(n + 2)\, C_{n+1} - (4n + 2)\, C_n = 0$ . Check for $n = 0, 1$ : $2 C_1 = 2 = 2 C_0$ and $3 C_2 = 6 = 6 C_1$ , with $C_0 = C_1 = 1$ and $C_2 = 2$ . Non-example: $u_{n+1} - 2^n u_n = 0$ fails the definition, since the coefficient $2^n$ is not a polynomial in $n$ . When all $p_i$ are constant, the recurrence has constant coefficients. If $p_r$ has a root $n_0 \in \N$ , the equation for $n = n_0$ does not determine $u_{n_0 + r}$ , so the initial values may not fix the solution. Other names are P-recursive or holonomic recurrence; an inhomogeneous version allows a polynomial right side.

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

Polynomial ring concept
Recurrence relation definition
Linear recurrence with polynomial coefficients definition

Tag	`4HH0RPA7E6`
URI	`m2://4HH0RPA7E6`
Kind	definition
Writing	W0 stub
MSC	39A06, 33F10
Defines	Linear recurrence with polynomial coefficients
Uses	Recurrence relation, Polynomial ring

Linear recurrence with polynomial coefficients

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here