Prove that $13/42\sum_{x=0}^{29} (x+1) \dfrac{{29\choose x}}{{41\choose x}} = 43/14$

binomial-coefficientscontest-mathdiscrete mathematicsprobabilitysummation

Prove that $13/42\sum_{x=0}^{29} (x+1) \dfrac{{29\choose x}}{{41\choose x}} = 43/14$.

If I were to guess a generalization, I'd say that for positive integers $m,n,$ with $m\leq n-1$ we have $\sum_{x=0}^m (x+1) \dfrac{{m\choose x}}{{n-1\choose x}} \dfrac{n-m}{n} = \dfrac{n+1}{n-m+1}.$ The latter sum can be described in probabilistic terms as the expected value of a certain random variable X, described as follows. Suppose we have a deck of $m$ red cards and $n-m>0$ blue cards and all cards are distinct. We shuffle the deck randomly so that each permutation is equally likely to occur. We then select the top card and remove it until we get a blue card. Let X be the number of cards we removed from the top.

The expected value calculation follows directly from the definition; the probability of drawing $x+1$ cards is $m(m-1)\cdots (m-x+1) (n-m) (n-x-1)!/n!,$ as there are $m(m-1)\cdots (m-x+1) $ ways to draw the first x red cards, $n-m$ ways to select the $(x+1)$th blue card, and $(n-x-1)!$ ways to arrange the remaining cards, and there are of course n! total permutations. Using the definition of expected value, we can easily obtain the required sum.

However evaluating the sum is another issue in itself, and I'm unsure of any good ways to make progress. It seems intuitive that the expected value would be $\dfrac{m}{n-m+1} + 1,$ but I'm not sure how to formally justify this.

I'm not sure if there are any useful binomial identities for proving the stated equality. I know some tricks involving binomial coefficients that involve integration and differentiation, but they don't seem useful for this problem (e.g. one can evaluate $\sum_{x=0}^n {n\choose x} \dfrac{1}{x+1}$ easily using integration and the resulting sum would be $\dfrac{2^{n+1}-1}{n+1}$).

Best Answer

Your generalization is correct.

Generalization. For $0\le m\leq n-1$, we have $\displaystyle\sum_{x=0}^m (x+1) \dfrac{{m\choose x}}{{n-1\choose x}} \dfrac{n-m}{n} = \dfrac{n+1}{n-m+1}.$

Proof. $$\text{LHS}=\frac{m!(n-m)!}{n!}\sum_{x=0}^m (x+1) {n-1-x\choose n-m-1}$$

$$\begin{aligned} &\quad\sum_{x=0}^m (x+1) {n-1-x\choose n-m-1} =\sum_{x=0}^m\left(\sum_{k=0}^x1\right){n-1-x\choose n-m-1}\\ &=\sum_{k=0}^m\sum_{x=k}^m{n-1-x\choose n-m-1} =\sum_{k=0}^m\sum_{i=n-m-1}^{n-1-k}{i\choose n-m-1}\\ &=\sum_{k=0}^m{n-k\choose n-m} =\sum_{i=n-m}^n{i\choose n-m}\\ &={n+1\choose n-m+1}, \end{aligned}$$ where each time we eliminate the summation index $i$, we are applying Christmas stocking identity. (Isn't today Christmas?!) (As shown in another answer, the above equality can be proved by double counting, too).

So $$\text{LHS}=\frac{m!(n-m)!}{n!}{n+1\choose n-m+1}=\text{RHS}.$$

Related Question