The absorption identity for binomial coefficients is 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.
Proof 2: A combinatorial argument.
Combinatorially, the absorption identity is probably better viewed in the form
In this reformulation, both sides count the number of ways to choose a chaired committee of size from total people. The left-hand side counts the number of ways to choose the committee members first and then choose a chair from those people. The right-hand side counts the number of ways to choose the chair first from people and then choose the remaining committee members from the remaining people.
The first summation identity [a two for one, really]
Let’s find the value of
The absorption identity works beautifully here, as it allows us to replace the factor of in the denominator with a factor of that does not depend on the summation index :
since the alternating sum of a row of binomial coefficients is .
[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 [See, for example, my answer here.]
The second summation identity
Let’s find the value of the similar sum
We can’t use the absorption identity directly here because we have in the denominator of the summand rather than . However, by combining finite differences and the recursion formula with the absorption identity we can find the sum.
Let . Then
Therefore,
where 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
For the full derivation, see my answer here.
This entry was posted in binomial coefficients, combinatorics. Bookmark the permalink.