## 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.