{{Short description|Transformation of a mathematical sequence}} 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''', {{math|''T''}}, of a sequence, {{math|{''a''<sub>''n''</sub>}<nowiki/>}}, is the sequence {{math|{''s''<sub>''n''</sub>}<nowiki/>}} defined by

<math display="block">s_n = \sum_{k=0}^n (-1)^k \binom{n}{k} a_k.</math>

Formally, one may write

<math display="block">s_n = (Ta)_n = \sum_{k=0}^n T_{nk} a_k</math>

for the transformation, where {{math|''T''}} is an infinite-dimensional operator with matrix elements {{math|''T''<sub>''nk''</sub>}}. The transform is an involution, that is,

<math display="block">TT = 1</math>

or, using index notation,

<math display="block">\sum_{k=0}^\infty T_{nk} T_{km} = \delta_{nm}</math>

where <math>\delta_{nm}</math> is the Kronecker delta. The original series can be regained by

<math display="block">a_n=\sum_{k=0}^n (-1)^k \binom{n}{k} s_k.</math>

The binomial transform of a sequence is just the {{mvar|n}}-th forward differences of the sequence, with odd differences carrying a negative sign, namely:

<math display="block">\begin{align} 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 \end{align}</math>

where {{math|Δ}} is the forward difference operator.

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

<math display="block">t_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} a_k</math>

whose inverse is

<math display="block">a_n=\sum_{k=0}^n \binom{n}{k} t_k.</math>

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==

Both versions of the binomial transform appear in difference tables. Consider the following difference table:

{| style=text-align:center |- | style="width:9%;"| 0 || style="width:9%;"| &nbsp; || style="width:9%;"| 1 || style="width:9%;"| &nbsp; || style="width:9%;"| 10 || style="width:9%;"| &nbsp; || style="width:9%;"| 63 || style="width:9%;"| &nbsp; || style="width:9%;"| 324 || style="width:9%;"| &nbsp; || style="width:9%;"| 1485 |- | &nbsp; || 1 || &nbsp; || 9 || &nbsp; || 53 || &nbsp; || 261 || &nbsp; || 1161 |- | &nbsp; || &nbsp; || 8 || &nbsp; || 44 || &nbsp; || 208 || &nbsp; || 900 |- | &nbsp; || &nbsp; || &nbsp; || 36 || &nbsp; || 164 || &nbsp; || 692 |- | &nbsp; || &nbsp; || &nbsp; || &nbsp; || 128 || &nbsp; || 528 |- | &nbsp; || &nbsp; || &nbsp; || &nbsp; || &nbsp; || 400 |}

Each line is the difference of the previous line. (The ''n''-th number in the ''m''-th line is ''a''<sub>''m'',''n''</sub> = 3<sup>''n''−2</sup>(2<sup>''m''+1</sup>''n''<sup>2</sup> + 2<sup>''m''</sup>(1+6''m'')''n'' + 2<sup>''m''-1</sup>9''m''<sup>2</sup>), and the difference equation ''a''<sub>''m''+1,''n''</sub> = ''a''<sub>''m'',''n''+1</sub> - ''a''<sub>''m'',''n''</sub> holds.)

The top line read from left to right is {''a''<sub>''n''</sub>} = 0, 1, 10, 63, 324, 1485, ... The diagonal with the same starting point 0 is {''t''<sub>''n''</sub>} = 0, 1, 8, 36, 128, 400, ... {''t''<sub>''n''</sub>} is the noninvolutive binomial transform of {''a''<sub>''n''</sub>}.

The top line read from right to left is {''b''<sub>''n''</sub>} = 1485, 324, 63, 10, 1, 0, ... The cross-diagonal with the same starting point 1485 is {''s''<sub>''n''</sub>} = 1485, 1161, 900, 692, 528, 400, ... {''s''<sub>''n''</sub>} is the involutive binomial transform of {''b''<sub>''n''</sub>}.

==Ordinary generating function== The transform connects the generating functions associated with the series. For the ordinary generating function, let

<math display="block">f(x) = \sum_{n=0}^\infty a_n x^n</math>

and

<math display="block">g(x) = \sum_{n=0}^\infty s_n x^n </math>

then

<math display="block">g(x) = (Tf)(x) = \frac{1}{1-x} f{\left(\frac{-x}{1-x}\right)}.</math>

==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

<math display="block">\sum_{n=0}^\infty {\left(-1\right)}^n a_n = \sum_{n=0}^\infty {\left(-1\right)}^n \frac{(\Delta^n a)_0}{2^{n+1}}</math>

which is obtained by substituting {{math|1=''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):

<math display="block">\sum_{n=0}^\infty {\left(-1\right)}^n \binom{n+p}{n} a_n = \sum_{n=0}^\infty {\left(-1\right)}^n \binom{n+p}{n} \frac{(\Delta^n a)_0}{2^{n+p+1}} ,</math>

where {{math|1=''p'' = 0, 1, 2,...}}.

The Euler transform is also frequently applied to the Euler hypergeometric integral <math>\,_2F_1</math>. Here, the Euler transform takes the form:

<math display="block">\,_2F_1 (a,b;c;z) = (1-z)^{-b} \,_2F_1 \left(c-a, b; c;\frac{z}{z-1} \right).</math>

[See <ref>{{cite journal|first1=Allen R.|last1=Miller|first2=R. B.|last2=Paris|title=Euler-type transformations for the generalized hypergeometric function|journal= Z. Angew. Math. Phys.|doi=10.1007/s00033-010-0085-0|year=2010|volume=62|number=1|pages=31–45|s2cid=30484300 |url=https://rke.abertay.ac.uk/en/publications/30e4ad50-271e-40a7-bfb3-dc6515871b50 }}</ref> for generalizations to other hypergeometric series.]

The binomial transform, and its variation as the Euler transform, is notable for its connection to the continued fraction representation of a number. Let <math>0 < x < 1</math> have the continued fraction representation

<math display="block">x=[0;a_1, a_2, a_3,\cdots]</math>

then

<math display="block">\frac{x}{1-x} = [0;a_1-1, a_2, a_3,\cdots]</math>

and

<math display="block">\frac{x}{1+x} = [0;a_1+1, a_2, a_3,\cdots].</math>

==Exponential generating function== For the exponential generating function, let

<math display="block">\overline{f}(x)= \sum_{n=0}^\infty a_n \frac{x^n}{n!}</math>

and

<math display="block">\overline{g}(x)= \sum_{n=0}^\infty s_n \frac{x^n}{n!}</math>

then

<math display="block">\overline{g}(x) = (T\overline{f})(x) = e^x \overline{f}(-x).</math>

The Borel transform will convert the ordinary generating function to the exponential generating function.

==Binomial convolution==

Let <math>(a_n)_{n\in\mathbb{N}}</math> and <math>(b_n)_{n\in\mathbb{N}}</math> be sequences of complex numbers. Their binomial convolution is defined by <math display="block"> (a\circ b)_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k},\ \ n=0,1,2,\ldots </math> 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 <math>\{e_n\}</math> defined by <math>e_0 = 1</math> and <math>e_n=0</math> for <math>n=1,2,\ldots,</math> serves as the identity under the binomial convolution. Further, it is easy to see that the sequences <math>\{a_n\}</math> with <math>a_0\ne 0</math> possess an inverse. Thus the set of sequences <math>\{a_n\}</math> with <math>a_0\ne 0</math> forms an abelian group under the binomial convolution.

The binomial convolution arises naturally from the product of the exponential generating functions. In fact, <math display="block"> \left( \sum^\infty_{n=0} a_n \frac{x^n}{n!} \right) \left( \sum^\infty_{n=0} b_n \frac{x^n}{n!} \right) = \sum^\infty_{n=0} (a\circ b)_n \frac{x^n}{n!}. </math>

The binomial transform can be written in terms of binomial convolution. Let <math>\lambda_n = (-1)^n</math> and <math>1_n=1</math> for all <math>n</math>. Then <math display="block"> (Ta)_n = (\lambda a\circ 1)_n. </math> The formula <math display="block">t_n = \sum_{k=0}^n {\left(-1\right)}^{n-k} \binom{n}{k} a_k \iff a_n = \sum_{k=0}^n \binom{n}{k} t_k</math> can be interpreted as a Möbius inversion type formula <math display="block">t_n = (a\circ \lambda)_n \iff a_n = (t\circ 1)_n</math> since <math>\lambda_n</math> is the inverse of <math>1_n</math> under the binomial convolution.

There is also another binomial convolution in the mathematical literature. The binomial convolution of arithmetical functions <math>f</math> and <math>g</math> is defined as <math display="block"> (f\circ_B g)(n) = \sum_{d\mid n} \left( \prod_p \binom{\nu_p(n)}{\nu_p(d)} \right) f(d)g(n/d), </math> where <math>n = \prod_p p^{\nu_p(n)}</math> is the canonical factorization of a positive integer <math>n</math> and <math>\binom{\nu_p(n)}{\nu_p(d)}</math> 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).

==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

<math display="block">u_n = \sum_{k=0}^n \binom{n}{k} a^k {\left(-c\right)}^{n-k} b_k</math>

gives

<math display="block">U(x) = \frac{1}{cx + 1} B{\left(\frac{ax}{cx+1}\right)}</math>

where {{math|''U''}} and {{math|''B''}} are the ordinary generating functions associated with the series <math>\{u_n\}</math> and <math>\{b_n\}</math>, respectively.

The rising {{mvar|k}}-binomial transform is sometimes defined as

<math display="block">\sum_{j=0}^n \binom{n}{j} j^k a_j.</math>

The falling {{mvar|k}}-binomial transform is

<math display="block">\sum_{j=0}^n \binom{n}{j} j^{n-k} a_j.</math>

Both are homomorphisms of the kernel of the Hankel transform of a series.

In the case where the binomial transform is defined as

<math display="block">\sum_{i=0}^n {\left(-1\right)}^{n-i} \binom{n}{i} a_i = b_n.</math>

Let this be equal to the function <math>\mathfrak J(a)_n=b_n.</math>

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 <math>\{b_n\}</math>, then the second binomial transform of the original sequence is,

<math display="block">\mathfrak J^2(a)_n=\sum_{i=0}^n(-2)^{n-i}\binom{n}{i}a_i.</math>

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

<math display="block">\mathfrak J^k(a)_n=b_n=\sum_{i=0}^n(-k)^{n-i}\binom{n}{i}a_i.</math>

Its inverse is,

<math display="block">\mathfrak J^{-k}(b)_n = a_n=\sum_{i=0}^n k^{n-i}\binom{n}{i}b_i.</math>

This can be generalized as,

<math display="block">\mathfrak J^k(a)_n = b_n = (\mathbf E-k)^na_0</math>

where <math>\mathbf E</math> is the shift operator.

Its inverse is

<math display="block">\mathfrak J^{-k}(b)_n = a_n = (\mathbf E+k)^nb_0.</math>

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

==References== {{Reflist}} * 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, [https://www.fq.math.ca/Scanned/32-5/prodinger.pdf Some information about the binomial transform], The Fibonacci Quarterly '''32''' (1994), 412–415. * {{cite journal|first1=Michael Z.|last1=Spivey |first2=Laura L.|last2=Steil|year=2006|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html|title= The k-Binomial Transforms and the Hankel Transform|journal=Journal of Integer Sequences|volume=9|page=06.1.1|bibcode=2006JIntS...9...11S }} * {{cite journal|last1=Borisov|first1=B.|last2=Shkodrov |first2=V.|year=2007|title=Divergent Series in the Generalized Binomial Transform|journal=Adv. Stud. Cont. Math.|volume=14|number=1|pages=77–82|url=https://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART001258138}} * 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).

==External links== *[http://mathworld.wolfram.com/BinomialTransform.html Binomial Transform] on Wolfram MathWorld *[https://oeis.org/wiki/Binomial_transform Binomial transform] in the OEIS wiki

Category:Transforms Category:Factorial and binomial topics Category:Hypergeometric functions