Recurrence relation
Difference operator and difference equations

The difference operator is an operator that maps sequences to sequences, and, more generally, functions to functions. It is commonly denoted Δ, {\displaystyle \Delta,} and is defined, in functional notation, as

It is thus a special case of finite difference.

When using the index notation for sequences, the definition becomes

The parentheses around Δ f {\displaystyle \Delta f} and Δ a {\displaystyle \Delta a} are generally omitted, and Δ a n {\displaystyle \Delta a_{n}} must be understood as the term of index n in the sequence Δ a, {\displaystyle \Delta a,} and not Δ {\displaystyle \Delta } applied to the element a n. {\displaystyle a_{n}.}

Given sequence a = (a n) n ∈ N, {\displaystyle a=(a_{n})_{n\in \mathbb {N} },} the first difference of a is Δ a. {\displaystyle \Delta a.}

The second difference is Δ 2 a = (Δ ∘ Δ) a = Δ (Δ a). {\displaystyle \Delta ^{2}a=(\Delta \circ \Delta)a=\Delta (\Delta a).} A simple computation shows that

More generally: the k th difference is defined recursively as Δ k = Δ ∘ Δ k − 1, {\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},} and one has

This relation can be inverted, giving

A difference equation of order k is an equation that involves the k first differences of a sequence or a function, in the same way as a differential equation of order k relates the k first derivatives of a function.

The two above relations allow transforming a recurrence relation of order k into a difference equation of order k, and, conversely, a difference equation of order k into recurrence relation of order k. Each transformation is the inverse of the other, and the sequences that are solution of the difference equation are exactly those that satisfies the recurrence relation.

For example, the difference equation

is equivalent to the recurrence relation

in the sense that the two equations are satisfied by the same sequences.

As it is equivalent for a sequence to satisfy a recurrence relation or to be the solution of a difference equation, the two terms "recurrence relation" and "difference equation" are sometimes used interchangeably. See Rational difference equation and Matrix difference equation for example of uses of "difference equation" instead of "recurrence relation"

Difference equations resemble differential equations, and this resemblance is often used to mimic methods for solving differentiable equations to apply to solving difference equations, and therefore recurrence relations.

Summation equations relate to difference equations as integral equations relate to differential equations. See time scale calculus for a unification of the theory of difference equations with that of differential equations.
detectable_content:number_placeholders[7]