I want to prove that the following equals 1: $W=\sum_{i=0}^{n-r}(-1)^i n \frac{C_{n-1}^{r-1}C_{n-r}^i}{(r+i)}$. I tried mathematical induction and succeeded. Is there any known identity of combinatorics that could be used to prove it directly?

  • $\begingroup$ I think the indices on your $C$'s are opposite of what they're supposed to be. Usually, the largest one is in top. $\endgroup$ – Arthur Aug 26 '18 at 12:13
  • $\begingroup$ Lots of factors in the sum don't depend on $i$, so you can move them out. Or did you mis type the equation? $\endgroup$ – darij grinberg Aug 26 '18 at 15:57
  • $\begingroup$ I agree with @dari grinbergj, it looks like a double sum with the condition $i+r=n$ $\endgroup$ – NivPai Aug 26 '18 at 16:29

If the question asked is (i.e., the first fraction inside the sum is $\frac{n}{r}$ instead of $\frac{n}{r+1}$) as follows, it makes sense. \begin{eqnarray*} \sum_{i+r=n}{ \frac{n}{r} \binom{n-1}{r-1} \binom{n-r}{i} (-1)^{i}} &=& 1\\ \end{eqnarray*}

This comes straightforward from multinomial expansion.

\begin{eqnarray*} \left(x_{1}+x_{2}+x_{3} \right)^{n} &=& \sum_{i+r=n}{\binom{n}{r,i} x_{1}^{i} x_{2}^{r}x_{3}^{n-r-i}} \\ \end{eqnarray*}

where $\binom{n}{r,i} =\frac{n!}{r! i! (n-r-i)}$

Choose $x_1=-1,x_{2}=x_{3}=1$, we will have, \begin{eqnarray*} \left(-1+1+1 \right)^{n} &=& \sum_{i+r=n}{\binom{n}{r,i} \left(-1\right)^{i} } \\ &=& \sum_{i+r=n}{ \frac{n}{r} \binom{n-1}{r-1} \binom{n-r}{i} (-1)^{i}} \\ \end{eqnarray*}

Note that,

\begin{eqnarray*} \frac{n}{r} \binom{n-1}{r-1} \binom{n-r}{i} &=& \frac{n}{r} \frac{(n-1)!}{(r-1)! (n-r)!} \frac{(n-r)!}{(i!)(n-r-i)!} \\ &=& \frac{(n)!}{(r)! (i!)(n-r-i)!} \\ &=& \binom{n}{r,i} \end{eqnarray*}

  • $\begingroup$ Thanks for that. The last edit was wrong. I changed to the original form. Can we still use this trick? $\endgroup$ – Daniel Aug 26 '18 at 19:52
  • $\begingroup$ If the sum were intended as you have it here and not as in the question, the term $\binom{n-r}{i}$ would be $\binom{n-r}{n-r}=1$. The sum would then be $$\sum_i\binom{n}{i}(-1)^i=0^n$$ which is $1$ when $n=0$, but $0$ when $n\gt0$. $\endgroup$ – robjohn Sep 23 '18 at 13:38

A Slightly More General Identity $$ \begin{align} \sum_k(-1)^k\frac{\binom{n}{k}}{\binom{r+k}{m}} &=\sum_k(-1)^k\frac{\binom{n-1}{k}+\binom{n-1}{k-1}}{\binom{r+k}{m}}\tag1\\ &=\sum_k(-1)^k\binom{n-1}{k}\left(\frac1{\binom{r+k}{m}}-\frac1{\binom{r+k+1}{m}}\right)\tag2\\ &=\sum_k(-1)^k\binom{n-1}{k}\left(\frac{\frac{r+k+1}{m+1}}{\binom{r+k+1}{m+1}}-\frac{\frac{r+k+1-m}{m+1}}{\binom{r+k+1}{m+1}}\right)\tag3\\ &=\frac{m}{m+1}\sum_k(-1)^k\frac{\binom{n-1}{k}}{\binom{r+k+1}{m+1}}\tag4\\ &=\frac{m}{m+n}\frac1{\binom{r+n}{m+n}}\tag5 \end{align} $$ Explanation:
$(1)$: Pascal's Rule
$(2)$: substitute $k\mapsto k+1$ in $(-1)^k\left.\binom{n-1}{k-1}\middle/\binom{r+k}{m}\right.$
$(3)$: put things over a common denominator
$(4)$: subtract and pull out the factor of $\frac{m}{m+1}$
$(5)$: repeat $n$ times

Application to the Question $$ \begin{align} \sum_{k=0}^{n-r}(-1)^kn\frac{\binom{n-1}{r-1}\binom{n-r}k}{r+k} &=n\binom{n-1}{r-1}\sum_{k=0}^{n-r}(-1)^k\frac{\binom{n-r}k}{\binom{r+k}{1}}\\ &=n\binom{n-1}{r-1}\frac1{n-r+1}\frac1{\binom{n}{n-r+1}}\\ &=n\binom{n-1}{r-1}\frac1n\frac1{\binom{n-1}{n-r}}\\[6pt] &=1 \end{align} $$


We show the validity of OPs claim \begin{align*} \sum_{i=0}^{n-r}(-1)^i\frac{n}{r+i}\binom{n-1}{r-1}\binom{n-r}{i}=1\qquad\qquad (0\leq r\leq n) \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-r}}&\color{blue}{(-1)^i\frac{n}{r+i}\binom{n-1}{r-1}\binom{n-r}{i}}\\ &=n\binom{n-1}{r-1}\sum_{i=0}^{n-r}\frac{(-1)^i}{r+i}\binom{n-r}{i}\tag{1}\\ &=n\binom{n-1}{r-1}\sum_{i=0}^{n-r}(-1)^i\binom{n-r}{i}\int_0^1x^{r+i-1}\,dx\tag{2}\\ &=n\binom{n-1}{r-1}\int_{0}^1x^{r-1}\sum_{i=0}^{n-r}(-1)^i\binom{n-r}{i}x^i\,dx\tag{3}\\ &=n\binom{n-1}{r-1}\int_0^1x^{r-1}(1-x)^{n-r}\,dx\tag{4}\\ &=\binom{n-1}{r-1}\binom{n-1}{r-1}^{-1}\tag{5}\\ &\,\,\color{blue}{=1} \end{align*} and the claim follows.


  • In (1) we factor out all terms independent from $i$.

  • In (2) we use $\int_0^1x^{k}\,dx=\frac{1}{k+1}$ with $k\ne -1$.

  • In (3) we do some rearrangements as preparation for the next step.

  • In (4) we apply the binomial theorem.

  • In (5) we apply the beta function identity $$ \binom{n}{r}^{-1}=(n+1)\int_0^1x^r(1-x)^{n-r}\,dx $$


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.