# How to prove this combinatorial identity?

I am wondering how to prove the following identity: $$\sum_{i=0}^{n-r} \frac{2^i (r+i) \binom{n-r}{i}}{(i+1) \binom{2n-r}{i+1}}=1?$$

It seems this might be related to the hypergeometric distribution, but I could not convert that form back into hypergeometric distribution form.

-
The first term has a zero denominator. –  Brian M. Scott Sep 7 '12 at 8:18
Where did you get that "identity" from? At least people should have some idea why one could have a reason to believe the identity (after correction) to hold. –  Marc van Leeuwen Sep 7 '12 at 8:32
It fails when $r=0$ (so that the $i$ in the denominator can be cancelled) and $n=1$: $$\frac{1\binom10}{\binom21}+\frac{2\binom11}{\binom22}=\frac12+2=\frac32$$ –  Brian M. Scott Sep 7 '12 at 9:01
@Rob: Even when dropping the $i=0$ term, I have yet to find a case $(n,r)$ where a useful result comes out. Please check the original problem statement carefully. –  Hagen von Eitzen Sep 7 '12 at 13:11
Sorry that that $i$ should $i+1$ –  Rob Sep 7 '12 at 18:54

Note that \begin{align} \frac{2^i(r+i)\binom{n-r}{i}}{(i+1) \binom{2n-r}{i+1}} &=\frac{2^i(r+i)}{n}\frac{\binom{2n-r-i-1}{n-1}}{\binom{2n-r}{n}}\tag{1}\\ &=\frac{2^i}{n}\frac{2n\binom{2n-r-i-1}{n-1}-n\binom{2n-r-i}{n}}{\binom{2n-r}{n}}\tag{2}\\ &=\frac{2^{i+1}\binom{2n-r-i-1}{n-1}-2^i\binom{2n-r-i}{n}}{\binom{2n-r}{n}}\tag{3} \end{align}
$(1)\quad$ $\frac1{i+1}\frac{\color{#C00000}{(n-r)!}}{i!\color{#C00000}{(n-r-i)!}}\frac{(i+1)!\color{#00A000}{(2n-r-i-1)!}}{\color{#00A000}{(2n-r)!}}=\frac1n\frac{n!\color{#C00000}{(n-r)!}}{\color{#00A000}{(2n-r)!}}\frac{\color{#00A000}{(2n-r-i-1)!}}{(n-1)!\color{#C00000}{(n-r-i)!}}$
$(2)\quad$ $\begin{array}{l}(2n-r-i)\binom{2n-r-i-1}{n-1}=n\binom{2n-r-i}{n}\\ \Rightarrow(r+i)\binom{2n-r-i-1}{n-1}=2n\binom{2n-r-i-1}{n-1}-n\binom{2n-r-i}{n}\end{array}$
$(3)\quad$ distribute $\frac{2^i}{n}$
Next, we have \begin{align} \sum_{k=0}^{n-m}\binom{n-k}{m}2^k &=\sum_{k=0}^{n-m}\sum_{j=0}^k\binom{n-k}{m}\binom{k}{j}\\ &=\sum_{j=0}^{n-m}\binom{n+1}{m+j+1}\tag{4} \end{align} Applying $(4)$ to the sum of $(3)$, we get to a nicely telescoping sum: \begin{align} {\large\sum_{i=0}^{n-r}}\;\frac{2^i(r+i)\binom{n-r}{i}}{(i+1) \binom{2n-r}{i+1}} &={\large\sum_{i=0}^{n-r}}\;\frac{2^{i+1}\binom{2n-r-i-1}{n-1}-2^i\binom{2n-r-i}{n}}{\binom{2n-r}{n}}\\ &=\frac1{\binom{2n-r}{n}}\sum_{i=0}^{n-r}\left(2\binom{2n-r}{n+i}-\binom{2n-r+1}{n+i+1}\right)\\ &=\frac1{\binom{2n-r}{n}}\sum_{i=0}^{n-r}\left(\binom{2n-r}{n+i}-\binom{2n-r}{n+i+1}\right)\\ &=\frac1{\binom{2n-r}{n}}\binom{2n-r}{n}\\[6pt] &=1\tag{5} \end{align}