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. 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 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. Both versions of the binomial transform appear in difference tables. Consider the following difference table: Each line is the difference of the previous line. (The n-th number in the m-th line is am,n = 3n−2(2m+1n2 + 2m(1+6m)n + 2m-19m2), and the difference equation am+1,n = am,n+1 - am,n holds.) The top line read from left to right is {an} = 0, 1, 10, 63, 324, 1485, ... The diagonal with the same starting point 0 is {tn} = 0, 1, 8, 36, 128, 400, ... {tn} is the noninvolutive binomial transform of {an}. The top line read from right to left is {bn} = 1485, 324, 63, 10, 1, 0, ... The cross-diagonal with the same starting point 1485 is {sn} = 1485, 1161, 900, 692, 528, 400, ... {sn} is the involutive binomial transform of {bn}. The transform connects the generating functions associated with the series. For the ordinary generating function, let and then The relationship between the ordinary generating functions is sometimes called the Euler transform.