3
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Sep 16 '19 at 23:34
1
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Sep 16 '19 at 23:33
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This helped me understand! Thanks! $\endgroup$ – Tim Sep 17 '19 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.