Binomial transform

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to the sequence associated with its ordinary generating function.

Definition[edit]

The binomial transform, T, of a sequence, {an}, is the sequence {sn} defined by

Formally, one may write

for the transformation, where T is an infinite-dimensional operator with matrix elements Tnk. The transform is an involution, that is,

or, using index notation,

where is the Kronecker delta. The original series can be regained by

The binomial transform of a sequence is just the nth forward differences of the sequence, with odd differences carrying a negative sign, namely:

where Δ is the forward difference operator.

Some authors define the binomial transform with an extra sign, so that it is not self-inverse:

whose inverse is

Example[edit]

Binomial transforms can be seen in difference tables. Consider the following:

0   1   10   63   324   1485
  1   9   53   261   1161
    8   44   208   900
      36   164   692
        128   528
          400

The top line 0, 1, 10, 63, 324, 1485,... (a sequence defined by (2n2 + n)3n − 2) is the (noninvolutive version of the) binomial transform of the diagonal 0, 1, 8, 36, 128, 400,... (a sequence defined by n22n − 1).

Shift states[edit]

The binomial transform is the shift operator for the Bell numbers. That is,

where the Bn are the Bell numbers.

Ordinary generating function[edit]

The transform connects the generating functions associated with the series. For the ordinary generating function, let

and

then

Euler transform[edit]

The relationship between the ordinary generating functions is sometimes called the Euler transform. It commonly makes its appearance in one of two different ways. In one form, it is used to accelerate the convergence of an alternating series. That is, one has the identity

which is obtained by substituting x=1/2 into the last formula above. The terms on the right hand side typically become much smaller, much more rapidly, thus allowing rapid numerical summation.

The Euler transform can be generalized (Borisov B. and Shkodrov V., 2007):

,

where p = 0, 1, 2,...

The Euler transform is also frequently applied to the Euler hypergeometric integral . Here, the Euler transform takes the form:

The binomial transform, and its variation as the Euler transform, is notable for its connection to the continued fraction representation of a number. Let have the continued fraction representation

then

and

Exponential generating function[edit]

For the exponential generating function, let

and

then

The Borel transform will convert the ordinary generating function to the exponential generating function.

Integral representation[edit]

When the sequence can be interpolated by a complex analytic function, then the binomial transform of the sequence can be represented by means of a Nörlund–Rice integral on the interpolating function.

Generalizations[edit]

Prodinger gives a related, modular-like transformation: letting

gives

where U and B are the ordinary generating functions associated with the series and , respectively.

The rising k-binomial transform is sometimes defined as

The falling k-binomial transform is

.

Both are homomorphisms of the kernel of the Hankel transform of a series.

In the case where the binomial transform is defined as

Let this be equal to the function

If a new forward difference table is made and the first elements from each row of this table are taken to form a new sequence , then the second binomial transform of the original sequence is,

If the same process is repeated k times, then it follows that,

Its inverse is,

This can be generalized as,

where is the shift operator.

Its inverse is

See also[edit]

References[edit]

External links[edit]