# How to show that $\sum\limits_{k=0}^n (-1)^k\tfrac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}} = \frac{x}{x+n}$

I'm trying to show that

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

I've tried expanding this using definition of binomial coefficient, then binomial expansion, now I'm using induction to simplify $\sum_{k=0}^m (-1)^k\frac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}}$, but it looks very inelegant, is there a better way?

Here is a variation based upon telescoping.

We obtain \begin{align*} \sum_{k=0}^n&(-1)^k\frac{\binom{n}{k}}{\binom{x+k}{k}}\\ &=\frac{1}{\binom{x+n}{n}}\sum_{k=0}^n(-1)^k\binom{x+n}{n-k}\tag{1}\\ &=\frac{1}{\binom{x+n}{n}}\left[\sum_{k=0}^{n-1}(-1)^k\left(\binom{x+n-1}{n-k}+\binom{x+n-1}{n-k-1}\right) +(-1)^n\right]\tag{2}\\ &=\frac{1}{\binom{x+n}{n}}\left[\sum_{k=0}^{n-1}(-1)^k\binom{x+n-1}{n-k}-\sum_{k=1}^n(-1)^{k}\binom{x+n-1}{n-k}+(-1)^n\right]\tag{3}\\ &=\frac{\binom{x+n-1}{n}}{\binom{x+n}{n}}\tag{4}\\ &=\frac{x}{x+n} \end{align*} and the claim follows.

Comment:

• In (1) we use $\binom{n}{k}\binom{x+k}{k}^{-1}=\binom{x+n}{n}^{-1}\binom{x+n}{n-k}$

• In (2) we use the binomial identity $\binom{p}{q}=\binom{p-1}{q}+\binom{p-1}{q-1}$

• In (3) we shift the index of the right-hand series by one

• In (4) we apply the telescoping

• Remarkable work. (+1): – Marko Riedel Dec 19 '16 at 21:30
• @MarkoRiedel: Thanks, Marko! :-) – Markus Scheuer Dec 19 '16 at 21:31
• @MarcoCantarini: Thanks Marco! I think each approach is instructive. (+1) – Markus Scheuer Dec 20 '16 at 8:21
• @MarkusScheuer This MSE link might have a formal power series argument. I am not sure there is a different proof strategy, but it would be interesting to see if it exists. – Marko Riedel Dec 22 '16 at 22:13

We recall the Melzak's identity $$f\left(x+y\right)=x\dbinom{x+n}{n}\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}\frac{f\left(y-k\right)}{x+k},\, x,y\in\mathbb{R},\, x\neq-k$$ where $f$ is an algebraic polynomial up to degree $n$. So taking $f\left(z\right)\equiv1$ we get $$\frac{1}{x\dbinom{x+n}{n}}=\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}\frac{1}{x+k}$$ hence, by the binomial inversion, we have $$\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}\frac{1}{\dbinom{x+k}{k}}=\color{red}{\frac{x}{x+n}}.$$

• Very Straightforward. (+1) – Hazem Orabi Dec 19 '16 at 11:13

A well-known identity related to the Beta function is $$\int_0^1 t^{p-1} (1-t)^{q-1} \; dt = \frac{\Gamma(p) \Gamma(q)}{\Gamma(p+q)}$$ from which we can easily derive $$\frac{1}{\binom{n}{k}} = (n+1)\int_0^1 t^k (1-t)^{n-k} \;dt$$ so $$\sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{\binom{x+k}{k}} = \sum_{k=0}^n (-1)^k \binom{n}{k} (x+k+1) \int_0^1 t^k (1-t)^x \;dt = I_1+I_2$$

where we define $$I_1 = \int_0^1 (1-t)^x x \sum_{k=0}^n (-1)^k \binom{n}{k} t^k \; dt$$ and $$I_2 = \int_0^1 (1-t)^x \sum_{k=0}^n (-1)^k \binom{n}{k} (k+1) t^k \; dt$$ In $I_1$, substitute $\sum_{k=0}^n (-1)^k \binom{n}{k} t^k = (1-t)^n$, with result $$I_1 = \int_0^1 x (1-t)^{n+x} \;dt = \frac{x}{(n+x)(1+n+x)}$$

Differentiating $t (1-t)^n =\sum_{k=0}^n (-1)^k \binom{n}{k} t^{k+1}$ with respect to $t$, we find $(1-t)^{n-1} [1 - (n+1)t] = \sum_{k=0}^n (-1)^k \binom{n}{k} (k+1) t^k$. Substituting into $I_2$, $$I_2 = \int_0^1 (1-t)^{x+n-1}[1-(n+1)t] \;dt =\frac{x}{1+n+x}$$ Combining these results and simplifying, we have $$I_1+I_2 = \frac{x}{x+n}$$ which is the desired result.

Another way to demonstrate this identity is to start from the expression of the Forward Delta $$\Delta _{\,x} ^{\,n} f(x) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,n - k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)f(x + k)}$$ Understanding the rising and falling factorials as actually expressed through the Gamma function, we have $$\Delta _{\,x} ^m \;x^{\,\underline {\,r\,} } = r^{\,\underline {\,m\,} } x^{\,\underline {\,r - m\,} }$$ Then $$\begin{gathered} f(x,n) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)/\left( \begin{gathered} x + k \\ k \\ \end{gathered} \right)} = \left( { - 1} \right)^{\,n} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {\left( { - 1} \right)^{\,n - k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)/\left( \begin{gathered} x + k \\ k \\ \end{gathered} \right)} = \hfill \\ = \left( { - 1} \right)^{\,n} \left. {\Delta _{\,y} ^{\,n} \left( {1/\left( \begin{gathered} x + y \\ y \\ \end{gathered} \right)} \right)\;} \right|_{\,y\, = \,0} = \left( { - 1} \right)^{\,n} \left. {\Delta _{\,y} ^{\,n} \left( {1/\left( \begin{gathered} x + y \\ x \\ \end{gathered} \right)} \right)\;} \right|_{\,y\, = \,0} = \hfill \\ = \left( { - 1} \right)^{\,n} \left. {\Delta _{\,y} ^{\,n} \left( {\frac{{x!}} {{\left( {x + y} \right)^{\,\underline {\,x\,} } }}} \right)\;} \right|_{\,y\, = \,0} = \left( { - 1} \right)^{\,n} x!\;\left. {\Delta _{\,y} ^{\,n} \left( {y^{\,\underline {\, - x\,} } } \right)\;} \right|_{\,y\, = \,0} = \hfill \\ = \left( { - 1} \right)^{\,n} x!\;\left( { - x} \right)^{\,\underline {\,n\,} } \left. {y^{\,\underline {\, - x - n\,} } \;} \right|_{\,y\, = \,0} = x!\;x^{\,\overline {\,n\,} } \left. {y^{\,\underline {\, - x - n\,} } \;} \right|_{\,y\, = \,0} = \hfill \\ = x!\;x^{\,\overline {\,n\,} } \frac{1} {{\left( {x + n} \right)!}}\; = \frac{{x\left( {x + n - 1} \right)!}} {{\left( {x + n} \right)!}} = \frac{x} {{x + n}} \hfill \\ \end{gathered}$$

This is an application of the Binomial Transform to the Partial Fraction Decomposition of $$\frac1{x\binom{x+n}{n}}=\frac{n!}{x(x+1)\cdots(x+n)}=\sum_{k=0}^n\frac{(-1)^k\binom{n}{k}}{x+k}\tag1$$ Equation $$(1)$$ can be derived easily using the Heaviside Method.

Since the Binomial Transform is its own inverse, applying it to $$(1)$$ gives $$\sum_{n=0}^m(-1)^n\binom{m}{n}\frac1{x\binom{x+n}{n}}=\frac1{x+m}\tag2$$ Multiplying $$(2)$$ by $$x$$ gives the desired result: $$\bbox[5px,border:2px solid #C0A000]{\sum_{n=0}^m(-1)^n\frac{\binom{m}{n}}{\binom{x+n}{n}}=\frac{x}{x+m}}\tag3$$

The Binomial Transform Is Its Own Inverse

Let $$b_n$$ be the Binomial Transform of $$a_k$$: $$b_n=\sum_{k=0}^n(-1)^k\binom{n}{k}a_k\tag4$$ then the Binomial Transform of $$b_n$$ is $$a_m$$: \begin{align} \sum_{n=0}^m(-1)^n\binom{m}{n}b_n &=\sum_{n=0}^m(-1)^n\binom{m}{n}\sum_{k=0}^n(-1)^k\binom{n}{k}a_k\tag{5a}\\ &=\sum_{k=0}^m\sum_{n=k}^m(-1)^{n+k}\binom{m}{n}\binom{n}{k}a_k\tag{5b}\\ &=\sum_{k=0}^m\sum_{n=k}^m(-1)^{n+k}\binom{m}{k}\binom{m-k}{n-k}[m\ge k]\,a_k\tag{5c}\\ &=\sum_{k=0}^m\binom{m}{k}[m=k]\,a_k\tag{5d}\\[6pt] &=a_m\tag5 \end{align} Explanation: [...] are Iverson brackets
$$\text{(5a)}$$: $$(4)$$
$$\text{(5b)}$$: change the order of summation
$$\text{(5c)}$$: $$\binom{m}{n}\binom{n}{k}=\binom{m}{k}\binom{m-k}{n-k}[m\ge k]$$
$$\text{(5d)}$$: $$\sum_{n=0}^{m-k}(-1)^n\binom{m-k}{n}[m\ge k]=(1-1)^{m-k}[m\ge k]=[m=k]$$
$$\phantom{a}\text{(5)}$$: evaluate