Sequence transformation

Classical examples for sequence transformations include the binomial transform, Möbius transform, Stirling transform and others.

For a given sequence

${\displaystyle S=\{s_{n}\}_{n\in \mathbb {N} },\,}$

the transformed sequence is

${\displaystyle \mathbf {T} (S)=S'=\{s'_{n}\}_{n\in \mathbb {N} },\,}$

where the members of the transformed sequence are usually computed from some finite number of members of the original sequence, i.e.

${\displaystyle s_{n}'=T(s_{n},s_{n+1},\dots ,s_{n+k})}$

for some ${\displaystyle k}$ which often depends on ${\displaystyle n}$ (cf. e.g. Binomial transform). In the simplest case, the ${\displaystyle s_{n}}$ and the ${\displaystyle s'_{n}}$ are real or complex numbers. More generally, they may be elements of some vector space or algebra.

In the context of acceleration of convergence, the transformed sequence is said to converge faster than the original sequence if

${\displaystyle \lim _{n\to \infty }{\frac {s'_{n}-\ell }{s_{n}-\ell }}=0}$

where ${\displaystyle \ell }$ is the limit of ${\displaystyle S}$, assumed to be convergent. In this case, convergence acceleration is obtained. If the original sequence is divergent, the sequence transformation acts as extrapolation method to the antilimit ${\displaystyle \ell }$.

If the mapping ${\displaystyle T}$ is linear in each of its arguments, i.e., for

${\displaystyle s'_{n}=\sum _{m=0}^{k}c_{m}s_{n+m}}$

for some constants ${\displaystyle c_{0},\dots ,c_{k}}$ (which may depend on n), the sequence transformation ${\displaystyle \mathbf {T} }$ is called a linear sequence transformation. Sequence transformations that are not linear are called nonlinear sequence transformations.

Simplest examples of (linear) sequence transformations include shifting all elements, ${\displaystyle s'_{n}=s_{n+k}}$ (resp. = 0 if n + k < 0) for a fixed k, and scalar multiplication of the sequence.

A less trivial example would be the discrete convolution with a fixed sequence. A particularly basic form is the difference operator, which is convolution with the sequence ${\displaystyle (-1,1,0,\ldots ),}$ and is a discrete analog of the derivative. The binomial transform is another linear transformation of a still more general type.

An example of a nonlinear sequence transformation is Aitken's delta-squared process, used to improve the rate of convergence of a slowly convergent sequence. An extended form of this is the Shanks transformation. The Möbius transform is also a nonlinear transformation, only possible for integer sequences.

• Aitken's delta-squared process
• Minimum polynomial extrapolation
• Richardson extrapolation
• Series acceleration
• Steffensen's method

• Hugh J. Hamilton, "Mertens' Theorem and Sequence Transformations", AMS (1947)

• Transformations of Integer Sequences, a subpage of the On-Line Encyclopedia of Integer Sequences