In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, the binomial transform is a
sequence transformation
In mathematics, a sequence transformation is an operator acting on a given space of sequences (a sequence space). Sequence transformations include linear mappings such as convolution with another sequence, and resummation of a sequence and, more ...
(i.e., a transform of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
) that computes its
forward difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the ...
s. 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
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
.
Definition
The binomial transform, ''T'', of a sequence, , is the sequence defined by
:
Formally, one may write
:
for the transformation, where ''T'' is an infinite-dimensional
operator with matrix elements ''T''
''nk''.
The transform is an
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
, that is,
:
or, using index notation,
:
where
is the
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 &\ ...
. The original series can be regained by
:
The binomial transform of a sequence is just the ''n''th
forward differences of the sequence, with odd differences carrying a negative sign, namely:
:
where Δ is the
forward difference operator
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the ...
.
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
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
.
Example
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 ''a''
''m'',''n'' = 3
''n''−2(2
''m''+1''n''
2 + 2
''m''(1+6''m'')''n'' + 2
''m''-19''m''
2), and the difference equation ''a''
''m''+1,''n'' = ''a''
''m'',''n''+1 - ''a''
''m'',''n'' holds.)
The top line read from left to right is = 0, 1, 10, 63, 324, 1485, ... The diagonal with the same starting point 0 is = 0, 1, 8, 36, 128, 400, ... is the noninvolutive binomial transform of .
The top line read from right to left is = 1485, 324, 63, 10, 1, 0, ... The cross-diagonal with the same starting point 1485 is = 1485, 1161, 900, 692, 528, 400, ... is the involutive binomial transform of .
Ordinary generating function
The transform connects the
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s associated with the series. For the
ordinary generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
, let
:
and
:
then
:
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
In mathematics, an alternating series is an infinite series of the form
\sum_^\infty (-1)^n a_n or \sum_^\infty (-1)^ a_n
with for all . The signs of the general terms alternate between positive and negative. Like any series, an alternatin ...
. 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
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
. 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
In mathematics, a continued fraction is an expression (mathematics), expression obtained through an iterative process of representing a number as the sum of its integer part and the multiplicative inverse, reciprocal of another number, then writ ...
representation of a number. Let
have the continued fraction representation
: