6
$\begingroup$

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.

  • 2
    The first term has a zero denominator.2012-09-07
  • 1
    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.2012-09-07
  • 0
    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$$2012-09-07
  • 0
    @Rob: ideas, insights, what have you done, background...?2012-09-07
  • 1
    @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.2012-09-07
  • 1
    Sorry that that $i$ should $i+1$2012-09-07
  • 0
    Mathematica comes up with this: $\frac{1}{(2 n-r-1) (2 n-r)}\left(r^2 (-\, _2F_1(1,r-n;-2 n+r+1;2))+2 n r \, _2F_1(1,r-n;-2 n+r+1;2)-2 r \, _2F_1(2,-n+r+1;-2 n+r+2;2)-r \, _2F_1(1,r-n;-2 n+r+1;2)+2 n \, _2F_1(2,-n+r+1;-2 n+r+2;2)\right)$2012-09-09
  • 0
    Sorry. I dropped this into the wrong spot.2012-09-09

1 Answers 1

6

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