Sum of the Reciprocals of the Binomial Coefficients

In this post we’re going to prove the following identity for the sum of the reciprocals of the numbers in column k of Pascal’s triangle, valid for integers $k \geq 2$:

Identity 1: $\displaystyle \sum_{n=k}^{\infty} \frac{1}{\binom{n}{k}} = \frac{k}{k-1}.$

The standard way to prove Identity 1 is is to convert the binomial coefficient in the denominator of the left side to an integral expression using the beta function, swap the integral and the summation, and pull some algebraic tricks with derivatives to sum the infinite series and then evaluate the integral.  (See, for example, the proof of Identity 107 on pages 77-78 of my upcoming Art of Proving Binomial Identities.)  In this post, though, we’re going to show how one can prove this identity using just three simple binomial identities:

Identity 2: $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+x} = \frac{n!}{x(x+1) \cdots (x+n)},$

Identity 3: $\displaystyle \sum_{k=0}^m \binom{n}{k} (-1)^k = (-1)^m \binom{n-1}{m},$

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

Identity 2 is your basic partial fractions decomposition formula when the factors in the denominator are consecutive integers.  Identity 3 gives the formula for the partial alternating row sum of the binomial coefficients.  Identity 4 is perhaps less well-known, but it does have a nice interpretation as two different ways of expressing the probability of drawing the red ball from a jar containing one red ball and n numbered blue balls.  (These are Identities 109, 20, and 24, respectively, in The Art of Proving Binomial Identities.)

On to the proof.

Proof of Identity 1.

First, let’s rewrite the summand of Identity 1 as a fraction with consecutive integer factors and apply Identity 2:

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

This gives the left side of Identity 1 as

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

Now, let’s transform the region of summation (just as we might transform the region of integration in a double integral) from an $(n,j)$ space to an $(i,j)$ space, where $i = j+n-k+1$.  The idea here is that we want to see what happens when we fix a particular denominator and sum over all the numerator expressions for that denominator.  The original region of summation in $(n,j)$ space looks like an infinite rectangle whose three finite sides are $n = k, j = 0$, and $j = k-1$.  The transformed region of summation looks like an infinite trapezoid whose three finite sides are $i = j+1, j = 0$, and $j = k-1$.  With the diagonal side $i = j+1$, we have to split the infinite series into two parts, one with i running from 1 to $k-1$ and one with i running from k to infinity.

Thus, we have $\displaystyle k \sum_{n=k}^{\infty} \sum_{j=0}^{k-1} \binom{k-1}{j} \frac{(-1)^j}{j + n - k+1} = k \sum_{i=1}^{k-1} \frac{1}{i} \sum_{j=0}^{i-1} \binom{k-1}{j} (-1)^j + k \sum_{i=k}^{\infty} \frac{1}{i} \sum_{j=0}^{k-1} \binom{k-1}{j} (-1)^j.$

Identity 3 tells us how to evaluate the two inner sums, leaving us (as the second inner sum is zero) with

$\displaystyle \sum_{n=k}^{\infty} \frac{1}{\binom{n}{k}} = k \sum_{i=1}^{k-1} \frac{1}{i} \sum_{j=0}^{i-1} \binom{k-1}{j} (-1)^j = k \sum_{i=1}^{k-1} \binom{k-2}{i-1}\frac{(-1)^{i-1}}{i} = k \sum_{i=0}^{k-2} \binom{k-2}{i}\frac{(-1)^i}{i+1} = \frac{k}{k-1},$

where the last step follows from Identity 4.