# Combinatorics sum to 1 using Identity

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?

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

• Thanks for that. The last edit was wrong. I changed to the original form. Can we still use this trick? – Daniel Aug 26 '18 at 19:52
• 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$. – 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.

Comment:

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