# Derive a Combinatorial Identity

An urn exists with $$x$$ red balls and $$y$$ green balls. Draw $$n$$ balls without replacement.

Derive a combinatorial identity for nonnegative integers $$n$$, $$x$$, and $$y$$, satisfying $$1 \leq n \leq x + y$$ from consideration of the following:

$$na = \sum_{k=0}^n k {n \choose k}a^k (1-a)^{n-k}$$

Attempt: I know that one side of the identity is $$n{x\over x+y}$$

Edit: The question is not to derive the na = ... identity above. It is to derive a new identity, using that identity as a guide, for drawing balls from the urn without replacement.

• Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. – N. F. Taussig Sep 16 '19 at 20:54

\begin{aligned} \sum^n_{k=0}k\binom{n}{k}a^k(1-a)^{n-k}&=\sum^n_{k=1}\frac{n(n-1)!}{(k-1)!(n-k)!}a^k(1-a)^{n-k}\\ &=na\sum^n_{k=1}\binom{n-1}{k-1}a^{k-1}(1-a)^{(n-1)-(k-1)}\\ &=na\sum^n_{k=0}\binom{n-1}{k}a^k(1-a)^{(n-1)-k}\\ &=na(a+1-a)^{n-1} \end{aligned}

• Thanks for your help. Does this satisfy 1 ≤ n ≤ x + y for the process of drawing balls without replacement for the urn?? One side of the identity is n(x/x+y). I am trying to derive the other half. – Tim Sep 16 '19 at 23:34

Oliver's answer is great, but just in case you like derivatives like me,

\begin{align} \frac{\partial}{\partial y}(x+y)^n = \sum_{k=0}^n { n \choose k} x^{n-k} \frac{\partial}{\partial y}y^k\newline n(x+y)^{n-1}=\sum_{k=0}^n { n \choose k} k x^{n-k} y^{k-1} \end{align}

Taking $$x = (1-a)$$ and $$y = a$$, $$x+y = 1$$,

\begin{align} na=\sum_{k=0}^n { n \choose k} k (1-a)^{n-k} a^{k} \end{align}

• Thanks for your help. Does this satisfy 1 ≤ n ≤ x + y for the process of drawing balls without replacement for the urn?? One side of the identity is n(x/x+y). I am trying to derive the other half. – Tim Sep 16 '19 at 23:33

The expression provided as reference is the expected number of balls, having prob. $$a$$ of being extracted with replacement from an urn containing a total of $$n$$ balls.

$$n x/(x+y)$$ is the expected number of balls "type x" in $$n$$ balls extracted without replacement from $$x+y$$ total balls: a sample mean.

You have $$\binom{x}{k}$$ ways to extract a $$k$$-subset from the set of $$x$$ balls (labelled) and $$\binom{y}{n-k}$$ to extract $$n-k$$ from the $$y$$. In total $$\sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,n} \right)} {\left( \matrix{ x \cr k \cr} \right)\left( \matrix{ y \cr n - k \cr} \right)} = \left( \matrix{ x + y \cr n \cr} \right)$$ ways.

Then $$n{x \over {x + y}} = {1 \over {\left( \matrix{ x + y \cr n \cr} \right)}}\sum\limits_{\left( {0\, \le } \right)k\,\left( { \le \,n} \right)} {k\left( \matrix{ x \cr k \cr} \right)\left( \matrix{ y \cr n - k \cr} \right)}$$

• This helped me understand! Thanks! – Tim Sep 17 '19 at 1:28