- Binomial transform
In
combinatorial mathematics the binomial transform is asequence transformation (ie, a transform of asequence ) that computes itsforward difference s. It is closely related to the Euler transform, which is the result of applying the binomial transform to the sequence associated with itsordinary 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 {nchoose 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}
where δ is the
Kronecker delta function . The original series can be regained by:a_n=sum_{k=0}^n (-1)^k {nchoose 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 = - ( riangle a)_0 = -a_1+a_0:s_2 = ( riangle^2 a)_0 = -(-a_2+a_1)+(-a_1+a_0) = a_2-2a_1+a_0:dots, :s_n = (-1)^n ( riangle^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} {nchoose k} a_k
whose inverse is
:a_n=sum_{k=0}^n {nchoose k} t_k.
hift states
The binomial transform is the
shift operator for theBell numbers . That is,:B_{n+1}=sum_{k=0}^n {nchoose k} B_k
where the B_n are the Bell numbers.
Ordinary generating function
The transform connects the
generating function s associated with the series. For theordinary 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} fleft(frac{-x}{1-x} ight).
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 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} ight)
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) = (Toverline{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 aNörlund-Rice integral on the interpolating function.Generalizations
Prodinger gives a related, modular-like transformation: letting
:u_n = sum_{k=0}^n {nchoose k} a^k (-c)^{n-k} b_k
gives
:U(x) = frac{1}{cx+1} Bleft(frac{ax}{cx+1} ight)
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 {nchoose j} j^k a_j
The falling "k"-binomial transform is
:sum_{j=0}^n {nchoose 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}inom{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}inom{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}inom{n}{i}a_i
It's inverse is,
:mathfrak J^{-k}(b)_n=a_n=sum_{i=0}^nk^{n-i}inom{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
It's inverse is
:mathfrak J^{-k}(b)_n=a_n=(mathbf E+k)^nb_0
ee also
*
Newton series
*Hankel matrix
*Möbius transform
*Stirling transform
*List of factorial and binomial topics References
* John H. Conway and Richard K. Guy, "The Book of Numbers", (1996)
* Donald E. Knuth, "The Art of Computer Programming Vol. 3", (1973) Addison-Wesley, Reading, MA.
* Helmut Prodinger, " [http://math.sun.ac.za/~prodinger/abstract/abs_87.htm Some information about the Binomial transform] ", (1992)
* Michael Z. Spivey and Laura L. Steil, " [http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.pdf The k-Binomial Transforms and the Hankel Transform] ", (2006)External links
* [http://mathworld.wolfram.com/BinomialTransform.html Binomial Transform]
Wikimedia Foundation. 2010.