Binomial transform

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

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

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

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

TT = 1 \,

or, using index notation,

\sum_{k=0}^\infty T_{nk}T_{km} = \delta_{nm}

where $\delta _{nm}$ is the Kronecker delta. 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 nth forward differences of the sequence, with odd differences carrying a negative sign, namely:

s_0 = a_0

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

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

\vdots\,

s_{n}=(-1)^{n}(\Delta ^{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.

In this case the former transform is called the inverse binomial transform, and the latter is just binomial transform. This is standard usage for example in On-Line Encyclopedia of Integer Sequences.

Example

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 (2n² + n)3^n − 2) is the (noninvolutive version of the) binomial transform of the diagonal 0, 1, 8, 36, 128, 400,... (a sequence defined by n²2^n − 1).

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}{x-1}}\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 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):

\sum_{n=0}^\infty (-1)^n {n+p\choose n} a_n = \sum_{n=0}^\infty (-1)^n {n+p\choose n}\frac {\Delta^n a_0} {2^{n+p+1}}

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

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

\,_2F_1 (a,b;c;z) = (1-z)^{-b} \,_2F_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.

In the case where the binomial transform is defined as

\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}a_i=b_n.

Let this be equal to the function $\mathfrak J(a)_n=b_n.$

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 $\{b_{n}\}$ , then the second binomial transform of the original sequence is,

\mathfrak J^2(a)_n=\sum_{i=0}^n(-2)^{n-i}\binom{n}{i}a_i.

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

\mathfrak J^k(a)_n=b_n=\sum_{i=0}^n(-k)^{n-i}\binom{n}{i}a_i.

Its inverse is,

\mathfrak J^{-k}(b)_n=a_n=\sum_{i=0}^nk^{n-i}\binom{n}{i}b_i.

This can be generalized as,

\mathfrak J^k(a)_n=b_n=(\mathbf E-k)^na_0

where $\mathbf {E}$ is the shift operator.

Its inverse is

\mathfrak J^{-k}(b)_n=a_n=(\mathbf E+k)^nb_0.

References

John H. Conway and Richard K. Guy, 1996, The Book of Numbers
Donald E. Knuth, The Art of Computer Programming Vol. 3, (1973) Addison-Wesley, Reading, MA.
Helmut Prodinger, 1992, Some information about the Binomial transform
Michael Z. Spivey and Laura L. Steil, 2006, The k-Binomial Transforms and the Hankel Transform
Borisov B. and Shkodrov V., 2007, Divergent Series in the Generalized Binomial Transform, Adv. Stud. Cont. Math., 14 (1): 77-82

External links

This article is issued from Wikipedia - version of the 11/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Binomial transform

Definition

Example

Ordinary generating function

Euler transform

Exponential generating function

Integral representation

Generalizations

See also

References

External links