## Shifts, Finite Differences, and Binomial Transforms

The binomial transform of a sequence $a_n$ is the sequence $b_n$ satisfying $\displaystyle b_n = \sum_{k=0}^n \binom{n}{k} a_k.$

In this post we prove the following:

Theorem: If $b_n$ is the binomial transform of $a_n$, then $\displaystyle \Delta^m b_n = \sum_{k=0}^n \binom{n}{k} a_{k+m}.$

In other words, the mth finite difference of $b_n$ is the binomial transform of the shifted sequence $a_{n+m}$.  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

$\displaystyle \Delta b_n = b_{n+1} - b_n = \sum_{k=0}^{n+1} \binom{n+1}{k} a_k - \sum_{k=0}^n \binom{n}{k} a_k = \sum_{k=0}^{n+1} \binom{n}{k-1} a_k = \sum_{k=0}^n \binom{n}{k} a_{k+1}.$

In the second-to-last step we use Pascal’s recurrence $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ plus the fact that $\binom{n}{n+1} = 0$.  In the last step we use $\binom{n}{-1} = 0$.

Therefore, $\displaystyle \Delta (\Delta b_n) = \sum_{k=0}^n \binom{n}{k} a_{k+2},$ and, in general, $\displaystyle \Delta^m b_n = \sum_{k=0}^n \binom{n}{k} a_{k+m}.$

Example: Start with the identity $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1}.$  (I’ve proved this identity three different ways so far on this blog: here, here, and here.)  Multiplying it by -1, we have $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k+1}}{k+1} = - \frac{1}{n+1}.$

Applying the theorem we just proved yields

$\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k+2}}{k+2} = - \frac{1}{n+2} + \frac{1}{n+1} = \frac{-(n+1) + (n+2)}{(n+1)(n+2)} = \frac{1}{(n+1)(n+2)}.$

Since $(-1)^{k+2} = (-1)^2 (-1)^k = (-1)^k$, this simplifies to

$\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+2} = \frac{1}{(n+1)(n+2)}.$

This identity can be generalized by taking $\displaystyle m-1$ finite differences.  I’ll leave it to the reader to prove the generalization

$\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+m} = \frac{n!}{m(m+1) \cdots (m+n)}.$