This site is supported by donations to The OEIS Foundation.

Binomial transform

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

Definition

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

${\displaystyle 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,

${\displaystyle 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 (bn) = (1, b, b², ...) yields the sequence ((b+1)n) = (1, b+1, (b+1)², ...). The proof is easy, actually this is nothing else than Newton's binomial formula for (1+b)n.) 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)n = (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, ...).