Editing Recurrence relation (section)

== Difference operator and difference equations {{anchor|Relationship to difference equations narrowly defined}} ==

The '''{{vanchor|difference operator}}''' is an [[operator (mathematics)|operator]] that maps [[sequence]]s to sequences, and, more generally, [[function (mathematics)|functions]] to functions. It is commonly denoted <math>\Delta,</math> and is defined, in [[functional notation]], as 
:<math>(\Delta f)(x)=f(x+1)-f(x).</math>
It is thus a special case of [[finite difference]].

When using the index notation for sequences, the definition becomes
:<math>(\Delta a)_n= a_{n+1} - a_n.</math>
The parentheses around <math>\Delta f</math> and <math>\Delta a</math> are generally omitted, and <math>\Delta a_n</math> must be understood as the term of index {{mvar|n}} in the sequence <math>\Delta a,</math> and not <math>\Delta</math> applied to the element <math>a_n.</math>

Given [[sequence]] <math>a=(a_n)_{n\in \N},</math> the '''{{vanchor|first difference}}''' of {{mvar|a}} is <math>\Delta a.</math>

The '''{{vanchor|second difference}}''' is 
<math>\Delta^2 a=(\Delta\circ\Delta)a= \Delta(\Delta a).</math> A simple computation shows that
:<math>\Delta^2 a_n= a_{n+2} - 2a_{n+1} + a_n.</math>

More generally: the  {{mvar|k}}''th difference'' is defined recursively as <math>\Delta^k=\Delta\circ \Delta^{k-1},</math> and one has
:<math>\Delta^k a_n = \sum_{t=0}^k (-1)^t \binom{k}{t} a_{n+k-t}.</math>

This relation can be inverted, giving
:<math>a_{n+k} = a_n + {k\choose 1} \Delta a_n  + \cdots + {k\choose k} \Delta^k(a_n).</math>

A '''{{vanchor|difference equation}}''' of order {{mvar|k}} is an equation that involves the {{mvar|k}} first differences of a sequence or a function, in the same way as a [[ordinary differential equation|differential equation]] of order {{mvar|k}} relates the {{mvar|k}} first [[derivative]]s of a function.

The two above relations allow transforming a recurrence relation of order {{mvar|k}} into a difference equation of order {{mvar|k}}, and, conversely, a difference equation of order {{mvar|k}} into recurrence relation of order {{mvar|k}}. Each transformation is the [[inverse function|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
:<math>3\Delta^2 a_n + 2\Delta a_n + 7a_n = 0</math>
is equivalent to the recurrence relation
:<math>3a_{n+2} = 4a_{n+1} - 8a_n,</math>
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 equation]]s relate to difference equations as [[integral equation]]s relate to differential equations. See [[time scale calculus]] for a unification of the theory of difference equations with that of differential equations.

===From sequences to grids===
Single-variable or one-dimensional recurrence relations are about sequences (i.e. functions defined on one-dimensional grids). Multi-variable or n-dimensional recurrence relations are about <math>n</math>-dimensional grids. Functions defined on <math>n</math>-grids can also be studied with partial difference equations.<ref>[https://books.google.com/books?id=1klnDGelHGEC Partial difference equations], Sui Sun Cheng, CRC Press, 2003, {{isbn|978-0-415-29884-1}}</ref>