# How can I implement the binomial transform?

How do I implement the binomial transform?

I've tried defining a matrix

P = Table[(-1)^k Binomial[n, k], {n, 0, m}, {k, 0, m}]


and having this act on my sequence (of length m + 1). But this seems quite crude. I shouldn't need to specify the length of my sequence.

Given the relationship to forward differences, can I implement it directly through Differences?

L = {a, b, c, d, e};
binT = NestList[Minus@*Differences, #, Length[#] - 1][[All, 1]] &;
binT[L]


{a, a - b, a - 2 b + c, a - 3 b + 3 c - d, a - 4 b + 6 c - 4 d + e}

Or this (longer, but uses less memory)

binT = Reap[Nest[(Sow[First[#]]; #)& @* Minus @* Differences,
(Sow[First[#]]; #), Length[#] - 1]][[2, 1]] &;


This OEIS page has a link to this file which gives the following code:

(* Difference Table (Binomial)  Transforms *)

BinomialTransform[{},___]={};
BinomialTransform[seq_List,way_:1]:=Table[Sum[way^(i - 1 - k)*Binomial[i - 1, k]*seq[[k + 1]], {k, 0, i - 1}],{i,1,Length[seq]}];
BinomialInvTransform[{},___]={};
BinomialInvTransform[seq_List,way_:1]:=BinomialTransform[seq,-way]


(Note that this BinomialTransform is the inverse of the one defined in the question and in wikipedia.)

For example,

 x=Table[n(3^n-2^n),{n,0,4}];
NestList[BinomialInvTransform,x,6]//TableForm


reproduces Jackson's difference fan of from page 86 of Conway and Guy's Book of Numbers:

0 1 10 57 260
0 1 8 30 88
0 1 6 9 12

• Sorry, to the other good answers, but I'm going to accept my own (taken from OEIS) as "canonical", ignoring elegance & efficiency. – pdmclean Aug 29 '17 at 0:09
ClearAll[f0, f1, f2, f3, f4]

f0[x_] := Module[{m = Length@x - 1}, Table[(-1)^k Binomial[n, k], {n, 0, m}, {k, 0, m}].x]
f1[x_] := Module[{r = Range[Length@x] - 1}, Outer[(-1)^#2 Binomial@## &, r , r].x]
f2[x_] := Module[{i = 0}, (-1)^(i++) Differences[x, #][] & /@ Range[0, Length @ x- 1]]
f3[x_] := Module[{r = Range[Length@x] - 1}, (-1)^r (Differences[x, #][] & /@ r)]
f4[x_] := MapIndexed[(-1)^(1 + #2[]) Differences[x, #2[] - 1][] &, x]


Examples:

f0 @ {a, b, c, d, e}


{a, a - b, a - 2 b + c, a - 3 b + 3 c - d, a - 4 b + 6 c - 4 d + e}

f0 @ Array[Subscript[y, #] &, {6}] Equal @@ (#@{a, b, c, d, e} & /@ {f0, f1, f2, f3, f4})


True

Equal @@ (#@Array[Subscript[y, #] &, {6}] & /@ {f0, f1, f2, f3, f4})


True