# A proof of the identity $\sum_{k = 0}^{n} \frac{(-1)^{k} \binom{n}{k}}{x + k} = \frac{n!}{(x + 0) (x + 1) \cdots (x + n)}$.

I have to prove that $$\forall n \in \mathbb{N}_{0}, ~ \forall x \in \mathbb{R} \setminus \mathbb{N}_{0}: \qquad \sum_{k = 0}^{n} \frac{(-1)^{k} \binom{n}{k}}{x + k} = \frac{n!}{(x + 0) (x + 1) \cdots (x + n)}.$$ However, I was unable to find a proof. I have tried to use the binomial expansion of $(1 + x)^{n}$ to get the l.h.s., by performing a suitable multiplication followed by integration, but I was unable to obtain the required form. Please help me out with the proof. Thanks in advance.

• I believe the right side should be $n! / [x(x+1) \cdots (x+n)]$. This actually does hold for $n = 0$. This appears to be a generalization of the partial fraction expansion $1/x(x+1) = 1/x - 1/(x+1)$. – Yakov Shklarov Sep 3 '16 at 2:26
• You need another factor of $x$ in the denominator of the righthand side. – Brian M. Scott Sep 3 '16 at 2:27
• (For the record, I typed out my answer before I saw @Winther's comment.) – arctic tern Sep 3 '16 at 2:51
• Note that the domain of both expressions is $\mathbb{R} \setminus \mathbb{N}_{0}$, not $\mathbb{R}$. – Transcendental Sep 4 '16 at 0:22

Write down the partial fraction decomposition

$$\frac{1}{x(x+1)\cdots(x+n)}=\sum_{k=0}^n \frac{c_k}{x+k}. \tag{\circ}$$

To determine the coefficient $c_k$, multiply by $x+k$ then compute the limit $x\to -k$, getting

$$c_k=\frac{1}{(-k)(1-k)(2-k)\cdots (-2)\cdot (-1)\cdot 1\cdot2\cdots(n-k)}=\frac{(-1)^k}{k!(n-k)!}$$

Substitute this into $(\circ)$, muliply both sides by $n!$, then use $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ to conclude.

\begin{align*} (1-t)^n = \sum_{k=0}^n (-1)^k \binom{n}{k} t^k \end{align*} Multiplying by $t^{x-1}$ and integrating between 0 and 1, we get \begin{align*} \int_0^1 t^{x-1}(1-t)^n dt = \sum_{k=0}^n (-1)^k \binom{n}{k}\frac{1}{x+k} \end{align*} and the left hand side is \begin{align*} \beta(x,n+1) &= \frac{\Gamma(x)\Gamma(n+1)}{\Gamma(x+n+1)} \end{align*} This simplifies to \begin{align*} \frac{n!}{x(x+1)(x+2)\ldots(x+n)} \end{align*}

• @YakovShklarov, Yes, you are correct. – user348749 Sep 3 '16 at 2:35

An induction on $n$ will work. Let

$$f(x,n)=\sum_{k=0}^n\frac{(-1)^k}{x+k}\binom{n}k\;,$$

and for the induction step suppose that

$$f(x,n)=\frac{n!}{x(x+1)\ldots(x+n)}\;.$$

Then

\begin{align*} \frac{(n+1)!}{x(x+1)\ldots(x+n+1)}&=\frac{n+1}{x+n+1}f(x,n)\\ &=\frac{n+1}{x+n+1}\sum_{k=0}^n\frac{(-1)^k}{x+k}\binom{n}k\\ &=(n+1)\sum_{k=0}^n(-1)^k\binom{n}k\frac1{(x+k)(x+n+1)}\\ &=(n+1)\sum_{k=0}^n\frac{(-1)^k}{n+1-k}\binom{n}k\left(\frac1{x+k}-\frac1{x+n+1}\right)\\ &=(n+1)\sum_{k=0}^n\frac{(-1)^k}{n+1}\binom{n+1}k\frac1{x+k}\\ &\qquad-\frac{n+1}{x+n+1}\sum_{k=0}^n\frac{(-1)^k}{n+1}\binom{n+1}k\\ &=\sum_{k=0}^n\frac{(-1)^k}{x+k}\binom{n+1}k-\frac1{x+n+1}\color{red}{\sum_{k=0}^n(-1)^k\binom{n+1}k}\\ &=f(x,n+1)-\frac{(-1)^{n+1}}{x+n+1}-\frac1{x+n+1}\color{red}{\left(0-(-1)^{n+1}\right)}\\ &=f(x,n+1)\;, \end{align*}

as desired.

• There is a question at this MSE link that would appear to be a match to your activity profile. – Marko Riedel Sep 3 '16 at 23:02

I thought it might be instructive to present a proof by induction.

First, we establish a base case. For $n=0$, it is straightforward to show that the expression holds.

Second, we assume that for some $n\geq 0$, we have

$$\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{x+k}=n!\prod_{k=0}^n\frac{1}{x+k}$$

Third, we analyze the sum $\sum_{k=0}^{n+1} \binom{n+1}{k}\frac{(-1)^k}{x+k}$. Clearly, we can write

\begin{align} \sum_{k=0}^{n+1} \binom{n+1}{k}\frac{(-1)^k}{x+k}&=\frac1x+\sum_{k=1}^{n} \binom{n+1}{k}\frac{(-1)^k}{x+k}+\frac{(-1)^{n+1}}{x+n+1}\\\\ &=\color{green}{\frac1x}+\sum_{k=1}^{n} \left(\color{green}{\binom{n}{k}}+\color{blue}{\binom{n}{k-1}}\right)\frac{(-1)^k}{x+k}+\color{red}{\frac{(-1)^{n+1}}{x+n+1}}\\\\ &=\color{green}{n!\prod_{k=0}^n\frac{1}{x+k}}+\color{blue}{\sum_{k=0}^{n-1} \binom{n}{k}\frac{(-1)^{k+1}}{(x+1)+k}}+\color{red}{\frac{(-1)^{n+1}}{x+n+1}}\\\\ &=\color{green}{n!\prod_{k=0}^n\frac{1}{x+k}}+\color{blue}{-n!\prod_{k=0}^n\frac{1}{x+1+k}-\frac{(-1)^{n+1}}{x+n+1}}+\color{red}{\frac{(-1)^{n+1}}{x+n+1}}\\\\ &=(n+1)!\prod_{k=0}^{n+1}\frac{1}{x+k} \end{align}

And we are done!

Remark. What follows is an exact duplicate of an earlier post of mine which I am unable to locate despite making a considerable effort.

We seek to verify that

$$\sum_{k=0}^n \frac{1}{x+k} (-1)^k {n\choose k} = n! \times \prod_{q=0}^n \frac{1}{x+q}.$$

Consider the function

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

where clearly $x$ is not equal to $0,-1,-2,\ldots -n$ or the LHS of the target formula becomes singular.

We compute the residues of $f(z).$ We get for the poles at $p\in [0,n]$ the residue

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

The residue at $z=-x$ yields

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

The residue at infinity is

$$\mathrm{Res}_{z=\infty} f(z) = - \mathrm{Res}_{z=0} \frac{1}{z^2} f(1/z) \\ = - \mathrm{Res}_{z=0} \frac{1}{z^2} n! \frac{1}{x+1/z} \prod_{q=0}^n \frac{1}{1/z-q} \\ = - \mathrm{Res}_{z=0} \frac{1}{z^2} n! \frac{z}{zx+1} \prod_{q=0}^n \frac{z}{1-qz} \\ = - \mathrm{Res}_{z=0} \frac{z^{n+2}}{z^2} n! \frac{1}{zx+1} \prod_{q=0}^n \frac{1}{1-qz} \\ = - \mathrm{Res}_{z=0} z^n n! \frac{1}{zx+1} \prod_{q=0}^n \frac{1}{1-qz} = 0.$$

To conclude observe that the residues sum to zero and collecting everything we obtain

$$\sum_{p=0}^n\frac{1}{x+p} (-1)^{n-p} {n\choose p} + n! (-1)^{n+1} \times \prod_{q=0}^n \frac{1}{x+q} = 0.$$

This is

$$\sum_{p=0}^n\frac{1}{x+p} (-1)^{p} {n\choose p} - n! \times \prod_{q=0}^n \frac{1}{x+q} = 0.$$

or

$$\sum_{p=0}^n\frac{1}{x+p} (-1)^{p} {n\choose p} = n! \times \prod_{q=0}^n \frac{1}{x+q}$$

which is the claim.