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)}.

Advertisements
This entry was posted in binomial coefficients, recurrence relations, sequences and series. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s