Proof of Alternating Binomial Coefficient Identity relating

Question

I am looking for a proof of the following binomial identity. I encountered it in an article on Euler’s derivation of the gamma function. Euler begins by evaluating the integral:

$$\int_0^1 x^a(1-x)^n\,dx$$

He performs a binomial expansion on the integrand and makes use of the following identity involving alternating binomial coefficients:

$$\sum_{k=0}^{n} (-1)^k {n \choose k} \frac{1}{a+k+1} = n! \prod_{k=0}^{n}\left( \frac{1}{a+k+1} \right).$$

It is not obvious to me on inspection that this formula is true, but I have found it cited elsewhere in the mathematical literature, without proof. I have verified it by hand for the cases of n=2 and n=3, but I am unable to prove the identity in general. I am looking for a good combinatorial or inductive proof of this very interesting fact.

I am aware that this formula relates to the beta function, but I am trying to derive this relationship without reference to this topic.

Thank you for enlightening me.

Answer 1

I am not quite sure if this counts as a duplicate but I give three proofs of an identity equivalent to this identity here (one of which is the beta function proof). I think it is cleanest to write it as

$$\sum_{k=0}^n \frac{(-1)^k}{z + k} {n \choose k} = \frac{n!}{z(z + 1) \dots (z + n)}$$

(here $z$ is $a+1$) which makes it clearer that for $n$ fixed it is an equality between two rational functions of $z$; in particular it holds for all complex values of $z \neq 0, -1, \dots -n$, and written this way it can be proven by calculating the residues at each pole of the RHS and verifying that they line up with the coefficients of the LHS. I give another proof via thinking of the LHS as the $n^{th}$ finite difference of the sequence $a_k = \frac{1}{z + k}$, which can be computed by induction and verified to line up with the RHS.

If we substitute $z \mapsto -\frac{1}{z}$ and clear denominators we get the equivalent identity

$$\sum_{k=0}^n \frac{(-1)^k}{1 - kz} {n \choose k} = \frac{n! z^n}{(1 - z) \dots (1 - nz)}$$

which is an ordinary generating function identity for the Stirling numbers of the second kind, and which can be proven by proving an exponential generating function identity and then translating it over.

Answer 2

By the partial fractions theorem, we know $$\frac{n!}{a(a+1) \cdots (a+n+1)} = \frac{b_0}{a} + \frac{b_1}{a+1} + \dots + \frac{b_{n+1}}{a+n+1}$$ for some set of numbers $b_0, b_1, \dots , b_{n+1}$. To find $b_k$, multiply both sides of the equation by $b+k$ and then set $a=-k$ in the resulting equation. The result is $$b_k = (-1)^k \binom{n}{k}$$

Answer 3

In trying to evaluate

$$S_n = \sum_{r=0}^n (-1)^r {n\choose r} \frac{1}{r+a+1}$$

where $a$ is not in $\{-1, -2, \ldots, -n-1\}$ we introduce

$$f(z) = \frac{(-1)^n \times n!}{z+a+1} \prod_{q=0}^n \frac{1}{z-q}$$

which has the property that for $0\le r\le n$

$$\mathrm{Res}_{z=r} f(z) = \frac{(-1)^n \times n!}{r+a+1} \prod_{q=0}^{r-1} \frac{1}{r-q} \prod_{q=r+1}^n \frac{1}{r-q} \\ = \frac{(-1)^n \times n!}{r+a+1} \frac{1}{r!} \frac{(-1)^{n-r}}{(n-r)!} = (-1)^r {n\choose r} \frac{1}{r+a+1}.$$

It follows that

$$S_n = \sum_{r=0}^n \mathrm{Res}_{z=r} f(z).$$

Now residues sum to zero and the residue at infinity of $f(z)$ is zero by inspection, therefore

$$S_n = - \mathrm{Res}_{z=-1-a} f(z) = (-1)^{n+1} \times n! \times \prod_{q=0}^n \frac{1}{-1-a-q} \\ = n! \prod_{q=0}^n \frac{1}{a+q+1}.$$

This is the claim.

Answer 4

I think that the "clearest" way to demonstrate the identity is through the finite differences and the Falling and Rising Factorial as follows

The finite difference (unitary step) of a function wrt to the variable $z$ is defined as $$ \Delta _{\,z} \,f(z) = f(z + 1) - f(z) $$ and its iteration becomes $$ \Delta _{\,z} ^{\,n} \,f(z) = \Delta _{\,z} \,\left( {\Delta _{\,z} ^{\,n - 1} \,f(z)} \right) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matrix{ n \cr k \cr} \right)\;f(z + k)} $$

Now, concerning the function $1/z$ we have $$ \eqalign{ & \Delta _{\,z} \left( {{1 \over z}} \right) = {1 \over {z + 1}} - {1 \over z} = {{ - 1} \over {z\left( {z + 1} \right)}} \cr & \Delta _{\,z} ^{\,2} \left( {{1 \over z}} \right) = \Delta _{\,z} \left( {\Delta _{\,z} \left( {{1 \over z}} \right)} \right) = {{\left( { - 1} \right)^{\,2} 2} \over {z\left( {z + 1} \right)\left( {z + 2} \right)}} \cr & \;\quad \vdots \cr & \Delta _{\,z} ^{\,n} \left( {{1 \over z}} \right) = \Delta _{\,z} ^{\,n} \left( {\left( {z - 1} \right)^{\,\underline {\, - 1\,} } } \right) = \left( { - 1} \right)^{\,\underline {\,n\,} } \left( {z - 1} \right)^{\,\underline {\, - 1 - n\,} } = {{\left( { - 1} \right)^{\,n} n!} \over {z^{\,\overline {\,n + 1\,} } }} \cr} $$ where the last line follows from the fundamental properties of the Falling and Rising Factorial represented respectively with $x^{\,\underline {\,k\,} } ,\quad x^{\,\overline {\,k\,} } $.

Putting the two together $$ \Delta _{\,z} ^{\,n} \left( {{1 \over z}} \right) = {{\left( { - 1} \right)^{\,n} n!} \over {z^{\,\overline {\,n + 1\,} } }} = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matrix{ n \cr k \cr} \right)\;{1 \over {z + k}}} \quad \left| {\;0 \le n \in Z} \right. $$