Binomial transform

This article needs more work.

Please help by expanding it!

The binomial transform is a bijective sequence transform based on convolution with binomial coefficients.

Definition

The binomial transform maps a sequence $\scriptstyle \{a_{0},a_{1},a_{2},...\}\,$ to and from a sequence $\scriptstyle \{b_{0},b_{1},b_{2},...\}\,$ via the 2-way mapping

$b_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a_{k},\ a_{n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}b_{k}\,.$

Matrix interpretation

Considering the sequences a, b as column vectors/matrices A, B, these transformations can be written as multiplication with the lower left triangular infinite square matrix P which consists in Pascal's triangle of binomial coefficients A007318, and its inverse A130595 which just differs in the signs of every other element,

$B=P\,A~,~~A=P^{-1}\,B~,~~P={\begin{pmatrix}1&0&0&0&\dots \\1&1&0&0&\dots \\1&2&1&0&\\[-.5ex]1&3&3&1&\ddots \\[-.5ex]1&4&6&4&\ddots \\[-.5ex]\vdots &\vdots &&&\ddots \end{pmatrix}}~,~~P^{-1}={\begin{pmatrix}1&0&0&0&\dots \\-1&1&0&0&\dots \\1&-2&1&0&\\[-.5ex]-1&3&-3&1&\ddots \\[-.5ex]1&-4&6&-4&\ddots \\[-.5ex]\vdots &\vdots &&&\ddots \end{pmatrix}}~.$

Examples

The binomial transform of the sequence (bⁿ) = (1, b, b², ...) yields the sequence ((b+1)ⁿ) = (1, b+1, (b+1)², ...). The proof is easy, actually this is nothing else than Newton's binomial formula for (1+b)ⁿ.) This includes the following special cases:

• b=1: The constant sequence A000012 = (1,1,1,1,...) transforms into the powers of 2, A000079 = (1, 2, 4, 8, 16,...).
• b=-1: The sequence (-1)ⁿ = (1,-1,1,-1,...) transforms into the sequence (1,0,0,0,...) = (0^n).
• b=2: The powers of 2, A000079 = (1, 2, 4, 8, 16,...), transform into powers of 3, A000244 = (1, 3, 9, 27, 81, 243, ...).

See also

• Sequence transforms
• Programs in Maple, Mathematica, PARI/GP, Sage

External links

• M. Bernstein and N. J. A. Sloane, Some Canonical Sequences of Integers, accepted for publication in "Linear Algebra and Its Applications" (Seidel Festschrift).

Authorship

• Daniel Forgues created this page on Aug 22 2010.
• M. F. Hasler provided matrix formulae, references to Pascal's triangle, binomial coefficients, OEIS sequences, links and other sections, on Nov 04 2014.

Cite this page as

D. Forgues and M. F. Hasler, Binomial transform. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki. (Available at https://oeis.org/wiki/Binomial_transform)