The binomial transform of a sequence is the sequence satisfying
In this post we prove the following:
Theorem: If is the binomial transform of , then
In other words, the mth finite difference of is the binomial transform of the shifted sequence . This theorem is useful because once we know one binomial coefficient identity in the form of a binomial transform we can use it to generate others.
Proof: First, we have
In the second-to-last step we use Pascal’s recurrence plus the fact that . In the last step we use .
Therefore, and, in general,
Applying the theorem we just proved yields
Since , this simplifies to
This identity can be generalized by taking finite differences. I’ll leave it to the reader to prove the generalization