Difference and functional equations Definition

Homogeneous and inhomogeneous linear recurrences

Definition

Let $K$ be a field and let $d \ge 1$ be an integer. Let $a_0, \dots, a_{d-1} \colon \N \to K$ and $g \colon \N \to K$ be sequences. A linear recurrence of order $d$ is the recurrence relation $u_{n+d} + a_{d-1}(n)\, u_{n+d-1} + \cdots + a_0(n)\, u_n = g(n) \qquad (n \in \N)$ for a sequence $u \colon \N \to K$ . The sequence $g$ is its right-hand side.

The recurrence is homogeneous if $g(n) = 0$ for all $n$ .
The recurrence is inhomogeneous if $g(n) \ne 0$ for some $n$ .
The associated homogeneous recurrence is the one with the same $a_0, \dots, a_{d-1}$ and with $g$ replaced by $0$ .

Remarks

Example: $u_{n+1} - 2 u_n = 1$ is inhomogeneous of order $1$ , with $a_0(n) = -2$ and $g(n) = 1$ . Its associated homogeneous recurrence is $u_{n+1} - 2 u_n = 0$ , whose solutions are $c\, 2^n$ . Non-example: $u_{n+1} = u_n^2 + 1$ is not a linear recurrence at all, since the term $u_n^2$ is not linear in $u_n$ ; so it is neither homogeneous nor inhomogeneous in this sense. When all $a_i$ are constant, the homogeneous case is a linear recurrence with constant coefficients. Other names are homogeneous and nonhomogeneous linear difference equations. The difference of two solutions of the inhomogeneous recurrence solves the associated homogeneous one.

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
Sequence concept
Homogeneous and inhomogeneous linear recurrences definition

Tag	`SVGN0QKE2C`
URI	`m2://SVGN0QKE2C`
Kind	definition
Writing	W0 stub
MSC	39A06, 39A05
Defines	Homogeneous and inhomogeneous linear recurrences
Uses	Recurrence relation, Sequence

Homogeneous and inhomogeneous linear recurrences

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here