Binomial transform

In mathematics, in the area of combinatorics, the binomial transform is a sequence transformation, that is, a transform of a sequence, by computing 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 the ordinary generating function. A special case of the Euler transform is sometimes used to accelerate the summation of alternating series (see series acceleration). Another special case is applied to the hypergeometric series.

Definition

The binomial transform, T, of a sequence, $\{a_{n}\}$, is the sequence $\{s_{n}\}$ defined by

$s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{k}$

Formally, one may write $(Ta)_{n}=s_{n}$ for the transformation, where T is an infinite-dimensional operator with matrix elements $T_{nk}$:

$s_{n}=(Ta)_{n}=\sum _{k=0}^{\infty }T_{nk}a_{k}$

The transform is an involution, that is,

$TT=1\,$

or, using index notation,

$\sum _{k=0}^{\infty }T_{nk}T_{km}=\delta _{nm}$

with δ being the Kronecker delta function. The original series can be regained by

$a_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}s_{k}$

The binomial transform of a sequence is just the n 'th forward difference of the sequence, namely

$s_{0}=a_{0}$

$s_{1}=-(\triangle a)_{0}=-a_{1}+a_{0}$

$s_{2}=(\triangle ^{2}a)_{0}=-(-a_{2}+a_{1})+(-a_{1}+a_{0})=a_{2}-2a_{1}+a_{0}$

. . .

$s_{n}=(-1)^{n}(\triangle ^{n}a)_{0}$

where Δ is the forward difference operator.

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

$t_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}a_{k}$

whose inverse is

$a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}$

Shift states

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

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$

where the $B_{n}$ are the Bell numbers.

Ordinary generating function

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

$f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}$

and

$g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}$

then

$g(x)=(Tf)(x)={\frac {1}{1-x}}f\left({\frac {-x}{1-x}}\right)$

Euler transform

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

$\sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\Delta ^{n}a_{0}}{2^{n+1}}}$

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

The Euler transform is also frequently applied to the hypergeometric series $\,_{2}F_{1}$. Here, the Euler transform takes the form:

$\,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(c-a,b;c;{\frac {z}{z-1}}\right)$

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

$x=[0;a_{1},a_{2},a_{3},\cdots ]$

then

${\frac {x}{1-x}}=[0;a_{1}-1,a_{2},a_{3},\cdots ]$

and

${\frac {x}{1+x}}=[0;a_{1}+1,a_{2},a_{3},\cdots ]$

Exponential generating function

For the exponential generating function, let

${\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}$

and

${\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}$

then

${\overline {g}}(x)=(T{\overline {f}})(x)=e^{x}{\overline {f}}(-x)$

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

Integral representation

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

Prodinger gives a related, modular-like transformation: letting

$u_{n}=\sum _{k=0}^{n}{n \choose k}a^{k}(-c)^{n-k}b_{k}$

gives

$U(x)={\frac {1}{cx+1}}B\left({\frac {ax}{cx+1}}\right)$

where U and B are the ordinary generating functions associated with the series $\{u_{n}\}$ and $\{b_{n}\}$, respectively.

The rising k-binomial transform is sometimes defined as

$\sum _{j=0}^{n}{n \choose j}j^{k}a_{j}$

The falling k-binomial transform is

$\sum _{j=0}^{n}{n \choose j}j^{n-k}a_{j}$.

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

See also

• Newton series
• Hankel matrix
• Möbius transform
• Stirling transform
• List of factorial and binomial topics

References

• Donald E. Knuth, The Art of Computer Programming Vol. 3, (1973) Addison-Wesley, Reading, MA.
• Helmut Prodinger, Some information about the Binomial transform, (1992)
• Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, (2006)