Combinatorics sum to 1 using Identity

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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