10
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Remarkable work. (+1): $\endgroup$ – Marko Riedel Dec 19 '16 at 21:30
  • $\begingroup$ @MarkoRiedel: Thanks, Marko! :-) $\endgroup$ – Markus Scheuer Dec 19 '16 at 21:31
  • $\begingroup$ @MarcoCantarini: Thanks Marco! I think each approach is instructive. (+1) $\endgroup$ – Markus Scheuer Dec 20 '16 at 8:21
  • $\begingroup$ @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. $\endgroup$ – Marko Riedel Dec 22 '16 at 22:13
6
$\begingroup$

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}}.$$

$\endgroup$
  • 1
    $\begingroup$ Very Straightforward. (+1) $\endgroup$ – Hazem Orabi Dec 19 '16 at 11:13
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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} $$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.