Incombinatorics, thebinomial transform is asequence transformation (i.e., a transform of asequence) that computes itsforward differences. It is closely related to theEuler transform, which is the result of applying the binomial transform to the sequence associated with itsordinary generating function.

Thebinomial transform,T, of a sequence,{a_n}, is the sequence{s_n} defined by

$${\displaystyle s_n=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})a_k.}$$ 

Formally, one may write

$${\displaystyle s_n=(Ta{)}_n=\sum _{k=0}^n{T}_{nk}{a}_k}$$ 

for the transformation, whereT is an infinite-dimensionaloperator with matrix elementsT_nk.The transform is aninvolution, that is,

$${\displaystyle TT=1}$$ 

or, using index notation,

$${\displaystyle \sum _{k=0}^{\mathrm{\infty }}{T}_{nk}{T}_{km}={\delta }_{nm}}$$ 

where${\displaystyle {\delta }_{nm}}$  is theKronecker delta. The original series can be regained by

$${\displaystyle a_n=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})s_k.}$$ 

The binomial transform of a sequence is just then-thforward differences of the sequence, with odd differences carrying a negative sign, namely:

 

whereΔ is theforward difference operator.

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

$${\displaystyle t_n=\sum _{k=0}^n(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})a_k}$$ 

whose inverse is

$${\displaystyle a_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})t_k.}$$ 

In this case the former transform is called theinverse binomial transform, and the latter is justbinomial transform. This is standard usage for example inOn-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. (Then-th number in them-th line isa_m,n = 3ⁿ⁻²(2^m+1n² + 2^m(1+6m)n + 2^m-19m²), and the difference equationa_m+1,n =a_m,n+1 -a_m,n holds.)

The top line read from left to right is {a_n} = 0, 1, 10, 63, 324, 1485, ... The diagonal with the same starting point 0 is {t_n} = 0, 1, 8, 36, 128, 400, ... {t_n} is the noninvolutive binomial transform of {a_n}.

The top line read from right to left is {b_n} = 1485, 324, 63, 10, 1, 0, ... The cross-diagonal with the same starting point 1485 is {s_n} = 1485, 1161, 900, 692, 528, 400, ... {s_n} is the involutive binomial transform of {b_n}.

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

$${\displaystyle f(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n}$$ 

and

$${\displaystyle g(x)=\sum _{n=0}^{\mathrm{\infty }}{s}_n{x}^n}$$ 

then

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

The relationship between the ordinary generating functions is sometimes called theEuler transform. It commonly makes its appearance in one of two different ways. In one form, it is used toaccelerate the convergence of analternating series. That is, one has the identity

$${\displaystyle \sum _{n=0}^{\mathrm{\infty }}{\left(-1\right)}^n{a}_n=\sum _{n=0}^{\mathrm{\infty }}{\left(-1\right)}^n\frac{({\mathrm{\Delta }}^{n}a{)}_0}{2^{n+1}}}$$ 

which is obtained by substitutingx = 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):

$${\displaystyle \sum _{n=0}^{\mathrm{\infty }}{\left(-1\right)}^n(\genfrac{}{}{0ex}{}{n+p}{n})a_n=\sum _{n=0}^{\mathrm{\infty }}{\left(-1\right)}^n(\genfrac{}{}{0ex}{}{n+p}{n})\frac{({\mathrm{\Delta }}^{n}a{)}_0}{2^{n+p+1}},}$$ 

wherep = 0, 1, 2,....

The Euler transform is also frequently applied to theEuler hypergeometric integral${\displaystyle {}_2{F}_1}$ . Here, the Euler transform takes the form:

$${\displaystyle {}_2{F}_1(a,b;c;z)=(1-z{)}^{-b}{}_2{F}_1\left(c-a,b;c;\frac{z}{z-1}\right).}$$ 

[See^[1] for generalizations to other hypergeometric series.]

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

$${\displaystyle x=[0;a_1,a_2,a_3,\cdots ]}$$ 

then

$${\displaystyle \frac{x}{1-x}=[0;a_1-1,a_2,a_3,\cdots ]}$$ 

and

$${\displaystyle \frac{x}{1+x}=[0;a_1+1,a_2,a_3,\cdots ].}$$ 

For theexponential generating function, let

$${\displaystyle \overline{f}(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{x^n}{n!}}$$ 

and

$${\displaystyle \overline{g}(x)=\sum _{n=0}^{\mathrm{\infty }}{s}_n\frac{x^n}{n!}}$$ 

then

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

TheBorel transform will convert the ordinary generating function to the exponential generating function.

Let${\displaystyle \{a_n\}}$  and${\displaystyle \{b_n\}}$ ,${\displaystyle n=0,1,2,\dots ,}$  be sequences of complex numbers. Their binomial convolution is defined by$${\displaystyle (a\circ b{)}_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a_k{b}_{n-k},n=0,1,2,\dots }$$ This convolution can be found in the book by R.L. Graham, D.E. Knuth and O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley (1989). It is easy to see that the binomial convolution is associative and commutative, and the sequence${\displaystyle \{e_n\}}$  defined by${\displaystyle e_0=1}$  and${\displaystyle e_n=0}$  for${\displaystyle n=1,2,\dots ,}$  serves as the identity under the binomial convolution. Further, it is easy to see that the sequences${\displaystyle \{a_n\}}$  with${\displaystyle a_0\ne 0}$  possess an inverse. Thus the set of sequences${\displaystyle \{a_n\}}$  with${\displaystyle a_0\ne 0}$  forms an Abelian group under the binomial convolution.

The binomial convolution arises naturally from the product of the exponential generating functions. In fact,$${\displaystyle \left(\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{x^n}{n!}\right)\left(\sum _{n=0}^{\mathrm{\infty }}{b}_n\frac{x^n}{n!}\right)=\sum _{n=0}^{\mathrm{\infty }}(a\circ b{)}_n\frac{x^n}{n!}.}$$ 

The binomial transform can be written in terms of binomial convolution. Let${\displaystyle {\lambda }_n=(-1{)}^n}$  and${\displaystyle 1_n=1}$  for all${\displaystyle n}$ . Then$${\displaystyle (Ta{)}_n=(\lambda a\circ 1{)}_n.}$$ The formula$${\displaystyle t_n=\sum _{k=0}^n{\left(-1\right)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})a_k⟺a_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})t_k}$$ can be interpreted as a Möbius inversion type formula$${\displaystyle t_n=(a\circ \lambda {)}_n⟺a_n=(t\circ 1{)}_n}$$ since${\displaystyle {\lambda }_n}$  is the inverse of${\displaystyle 1_n}$  under the binomial convolution.

There is also another binomial convolution in the mathematical literature. The binomial convolution of arithmetical functions${\displaystyle f}$  and${\displaystyle g}$  is defined as$${\displaystyle (f{\circ }_{B}g)(n)=\sum _{d\mid n}\left(\prod _p(\genfrac{}{}{0ex}{}{{\nu }_p(n)}{{\nu }_p(d)})\right)f(d)g(n/d),}$$ where${\displaystyle n=\prod _p{p}^{{\nu }_p(n)}}$  is the canonical factorization of a positive integer${\displaystyle n}$  and${\displaystyle (\genfrac{}{}{0ex}{}{{\nu }_p(n)}{{\nu }_p(d)})}$  is the binomial coefficient. This convolution appears in the book by P. J. McCarthy (1986) and was further studied by L. Toth and P. Haukkanen (2009).

When the sequence can be interpolated by acomplex analytic function, then the binomial transform of the sequence can be represented by means of aNörlund–Rice integral on the interpolating function.

Prodinger gives a related,modular-like transformation: letting

$${\displaystyle u_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{\left(-c\right)}^{n-k}{b}_k}$$ 

gives

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

whereU andB are the ordinary generating functions associated with the series${\displaystyle \{u_n\}}$  and${\displaystyle \{b_n\}}$ , respectively.

The risingk-binomial transform is sometimes defined as

$${\displaystyle \sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})j^k{a}_j.}$$ 

The fallingk-binomial transform is

$${\displaystyle \sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})j^{n-k}{a}_j.}$$ 

Both are homomorphisms of thekernel of theHankel transform of a series.

In the case where the binomial transform is defined as

$${\displaystyle \sum _{i=0}^n{\left(-1\right)}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})a_i=b_n.}$$ 

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

If a newforward difference table is made and the first elements from each row of this table are taken to form a new sequence${\displaystyle \{b_n\}}$ , then the second binomial transform of the original sequence is,

$${\displaystyle {\mathfrak{J}}^2(a{)}_n=\sum _{i=0}^n(-2{)}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})a_i.}$$ 

If the same process is repeatedk times, then it follows that,

$${\displaystyle {\mathfrak{J}}^k(a{)}_n=b_n=\sum _{i=0}^n(-k{)}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})a_i.}$$ 

Its inverse is,

$${\displaystyle {\mathfrak{J}}^{-k}(b{)}_n=a_n=\sum _{i=0}^n{k}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})b_i.}$$ 

This can be generalized as,

$${\displaystyle {\mathfrak{J}}^k(a{)}_n=b_n=(\mathbf{E}-k{)}^n{a}_0}$$ 

where${\displaystyle \mathbf{E}}$  is theshift operator.

Its inverse is

$${\displaystyle {\mathfrak{J}}^{-k}(b{)}_n=a_n=(\mathbf{E}+k{)}^n{b}_0.}$$ 

• Newton series
• Hankel matrix
• Möbius transform
• Stirling transform
• Euler summation
• Binomial QMF
• Riemann–Liouville integral
• List of factorial and binomial topics

• 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,Some information about the binomial transform, The Fibonacci Quarterly32 (1994), 412-415.
• Spivey, Michael Z.; Steil, Laura L. (2006)."The k-Binomial Transforms and the Hankel Transform".Journal of Integer Sequences.9: 06.1.1.Bibcode:2006JIntS...9...11S.
• Borisov, B.; Shkodrov, V. (2007)."Divergent Series in the Generalized Binomial Transform".Adv. Stud. Cont. Math.14 (1):77–82.
• Khristo N. Boyadzhiev,Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.
• R.L. Graham, D.E. Knuth and O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley (1989).
• P. J. McCarthy, Introduction to Arithmetical Functions, Springer-Verlag, 1986.
• P. Haukkanen, On a binomial convolution of arithmetical functions, Nieuw Arch. Wisk. (IV) 14 (1996), no. 2, 209--216.
• L. Toth and P. Haukkanen, On the binomial convolution of arithmetical functions, J. Combinatorics and Number Theory 1(2009), 31-48.
• P. Haukkanen, Some binomial inversions in terms of ordinary generating functions. Publ. Math. Debr. 47, No. 1-2, 181-191 (1995).

• Binomial Transform
• Transformations of Integer Sequences