The Absorption Identity for Binomial Coefficients

The absorption identity for binomial coefficients is \displaystyle \binom{n}{k} \frac{n+1}{k+1} = \binom{n+1}{k+1}.  This post will give a couple of proofs of the identity and then use it to prove some other identities involving binomial coefficient sums.

Proofs of the absorption identity

Proof 1: Use the factorial definition of the binomial coefficients.

\displaystyle \binom{n}{k} \frac{n+1}{k+1} = \frac{n!}{k! (n-k)!} \frac{n+1}{k+1} = \frac{(n+1)!}{(k+1)! (n + 1 - (k+1))!} = \binom{n+1}{k+1}.

Proof 2: A combinatorial argument.

Combinatorially, the absorption identity is probably better viewed in the form \displaystyle \binom{n+1}{k+1} (k+1) = \binom{n}{k} (n+1).

In this reformulation, both sides count the number of ways to choose a chaired committee of size k+1 from n+1 total people.  The left-hand side counts the number of ways to choose the k+1 committee members first and then choose a chair from those k+1 people.  The right-hand side counts the number of ways to choose the chair first from n+1 people and then choose the remaining k committee members from the remaining n people.

The first summation identity (a two for one, really)

Let’s find the value of \displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1}.

The absorption identity works beautifully here, as it allows us to replace the factor of k+1 in the denominator with a factor of n+1 that does not depend on the summation index k:

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1} (-1)^k = \frac{1}{n+1} \sum_{k=1}^{n+1} \binom{n+1}{k} (-1)^{k+1} = \frac{1}{n+1} \left( \sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{k+1} + 1 \right) = \frac{1}{n+1},

since the alternating sum of a row of binomial coefficients is 0.

(At this math.SE question André Nicolas gives a different proof using integration and the binomial formula, and I give a probabilistic proof that uses inclusion-exclusion.)

A similar argument shows that \displaystyle \sum_{k=1}^n \binom{n}{k} \frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}.   (See, for example, my answer here.)

The second summation identity 

Let’s find the value of the similar sum \displaystyle \sum_{k=1}^n \binom{n}{k} \frac{(-1)^k}{k}.

We can’t use the absorption identity directly here because we have k in the denominator of the summand rather than k+1.  However, by combining finite differences and the recursion formula \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1} with the absorption identity we can find the sum.

Let \displaystyle f(n) = \sum_{k=1}^n \binom{n}{k} \frac{(-1)^k}{k}.  Then

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

Therefore, \displaystyle \sum_{k=1}^n \binom{n}{k} \frac{(-1)^k}{k} = f(n) = \sum_{k=1}^n \big( f(k) - f(k-1) \big) = \sum_{k=1}^n \frac{-1}{k} = - H_n,

where H_n is the nth harmonic number.

A bonus summation identity

Applying the absorption identity twice with the ideas in the derivation of the previous identity shows that

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

For the full derivation, see my answer here.

Advertisements
This entry was posted in binomial coefficients, combinatorics. Bookmark the permalink.

3 Responses to The Absorption Identity for Binomial Coefficients

  1. Pingback: A Probabilistic Proof of a Binomial Coefficient Identity | A Narrow Margin

  2. Pingback: Shifts, Finite Differences, and Binomial Transforms | A Narrow Margin

  3. Pingback: Two Methods for Proving an Alternating Binomial Identity | A Narrow Margin

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