7
$\begingroup$

For a probability problem, I ended up with the following expression $$\sum_{k=0}^nk\ \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k$$ Using Mathematica I've found that the result should be $\frac{n}{3}$. However, I have no idea how to get there. Any ideas?

$\endgroup$
  • $\begingroup$ Solve the following question in two different ways - using binomial-distribution, and using the direct approach: when rolling a fair $6$-sided die $n$ times, what is the expected number of times that we get $1$ or $2$? The answer using the first approach is the expression in your question, and the answer using the second approach is the result you've found. $\endgroup$ – barak manos May 24 '16 at 14:17
8
$\begingroup$

\begin{align*} \sum_{k=0}^n k \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k &=\sum_{k=0}^n k\frac{n!}{k!(n-k)!}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &=\sum_{k=0}^n \frac{n!}{(k-1)!(n-k)!}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &=\frac{n}{3}\sum_{k=0}^n \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}\left(\frac{2}{3}\right)^{(n-1)-(k-1)}\left(\frac{1}{3}\right)^{k-1}\\ &=\frac{n}{3}\sum_{k=0}^n \binom{n-1}{k-1}\left(\frac{2}{3}\right)^{(n-1)-(k-1)}\left(\frac{1}{3}\right)^{k-1}\\ &=\frac{n}{3}\left(\frac{2}{3}+\frac{1}{3}\right)^{n-1}\\ &=\frac{n}{3}. \end{align*} The second to last line is a result of the binomial theorem.


Edit: It was pointed out that I need to be careful when $k=0$. I also made a mistake in applying the binomial theorem. Here is a revised proof. Note that when $k=0$, the term of the sum is $0$, so it is the same as starting at $k=1$.

\begin{align*} \sum_{k=0}^n k \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k &= \sum_{k=1}^n k \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &= \sum_{k=1}^n k \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &=\sum_{k=1}^n k\frac{n!}{k!(n-k)!}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &=\sum_{k=1}^n \frac{n!}{(k-1)!(n-k)!}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^k\\ &=\frac{n}{3}\sum_{k=1}^n \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}\left(\frac{2}{3}\right)^{(n-1)-(k-1)}\left(\frac{1}{3}\right)^{k-1}\\ &=\frac{n}{3}\sum_{k=1}^n \binom{n-1}{k-1}\left(\frac{2}{3}\right)^{(n-1)-(k-1)}\left(\frac{1}{3}\right)^{k-1}\\ &=\frac{n}{3}\sum_{k=0}^{n-1} \binom{n-1}{k}\left(\frac{2}{3}\right)^{(n-1)-k}\left(\frac{1}{3}\right)^{k}\\ &=\frac{n}{3}\left(\frac{2}{3}+\frac{1}{3}\right)^{n-1}\\ &=\frac{n}{3}. \end{align*}

$\endgroup$
  • 1
    $\begingroup$ Perhaps I'm unfamiliar with some notation abuse or shortcuts common in dealing with $\binom{n}{k}$, but $(k-1)!$ is undefined when $k=0$ (lines 2 through 4). $\endgroup$ – Turambar May 24 '16 at 18:56
  • $\begingroup$ @Turambar Indeed. But the $k = 0$ term is $0$ so we could just change the bounds of the sum to $\sum_{k=1}^n$ and everything works. $\endgroup$ – Tavian Barnes May 24 '16 at 19:20
  • 1
    $\begingroup$ @Turambar Thank you for pointing out that subtlety. I've revised my answer to reflect your comment. $\endgroup$ – kccu May 24 '16 at 19:24
  • $\begingroup$ @Turambar One can make the statement $\frac1{(-n)!}=0$ for $n\in\mathbb{N}$ $\endgroup$ – Simply Beautiful Art May 24 '16 at 20:53
  • $\begingroup$ You have an error in the third to last line of your revision. After you substituted $k$ for $k-1$ and adjusted the range of the sum, you replaced the $n-1$ terms with $n$. These should remain as $n-1$, and you will get $(\frac{2}{3} + \frac{1}{3})^{n-1}$, as you had originally. $\endgroup$ – Matthew May 25 '16 at 0:00
16
$\begingroup$

Consider the function $$f\left(x\right)=\left(\frac{2}{3}+x\right)^{n}. $$ By the binomial theorem we have $$f\left(x\right)=\sum_{k=0}^{n}\dbinom{n}{k}\left(\frac{2}{3}\right)^{n-k}x^{k} $$ so if we take the derivative and we multiply by $x$ we have $$xf'\left(x\right)=\sum_{k=0}^{n}k\dbinom{n}{k}\left(\frac{2}{3}\right)^{n-k}x^{k} $$ so $$\sum_{k=0}^{n}k\dbinom{n}{k}\left(\frac{2}{3}\right)^{n-k}x^{k}=nx\left(\frac{2}{3}+x\right)^{n-1} $$ now take $x=\frac{1}{3}$.

$\endgroup$
  • $\begingroup$ Sorry, I didn't check it . I've deleted my answer. $\endgroup$ – SchrodingersCat May 24 '16 at 14:16
  • $\begingroup$ @SchrodingersCat No problem ;) $\endgroup$ – Marco Cantarini May 24 '16 at 14:19
  • 1
    $\begingroup$ +1 At first sight, this might look like a one-time trick out of the blue with no use outside this particular problem, but actually similar methods are very common in combinatorics, so it's good to learn these. (Perhaps more common than direct computations?) $\endgroup$ – JiK May 25 '16 at 10:26
6
$\begingroup$

Just some binomial coefficient massage and the binomial formula: $$ \sum_{k=0}^nk\binom nkx^{n-k}y^k =\sum_{k=1}^nn\binom{n-1}{k-1}x^{n-k}y^k =ny(x+y)^{n-1} $$ Now plug in $x=\frac23$ and $y=\frac13$.

$\endgroup$
3
$\begingroup$

Hint: $$k\binom{n}{k}=n\binom{n-1}{k-1}$$

$\endgroup$
3
$\begingroup$

You can solve the following question in two different ways:

  • Using binomial distribution
  • Using the direct approach

When rolling a fair $6$-sided die $n$ times, what is the expected number of times we get "1" or "2"?


Using binomial distribution, we split it into disjoint events and then add up their probabilities:

  • The probability of getting "1" or "2" in a single roll is $\frac13$
  • The probability of getting "1" or "2" in exactly $k$ out of $n$ rolls is $\binom{n}{k}\cdot\left(\frac13\right)^{k}\cdot\left(1-\frac13\right)^{n-k}$
  • The expected number of times we get "1" or "2" in $n$ rolls is $\sum\limits_{k=0}^{n}k\cdot\binom{n}{k}\cdot\left(\frac13\right)^{k}\cdot\left(1-\frac13\right)^{n-k}$

Using the direct approach, we expect to get "1" or "2" exactly $\frac13$ of the time, i.e., in $\frac{n}{3}$ out of $n$ rolls.


Therefore:

$$\sum\limits_{k=0}^{n}k\cdot\binom{n}{k}\cdot\left(\frac13\right)^{k}\cdot\left(1-\frac13\right)^{n-k}=\frac{n}{3}$$

$\endgroup$
  • $\begingroup$ I'm not sure whether or not this answer qualifies mathematically... would be glad if somebody could comment in order to confirm or reject it... $\endgroup$ – barak manos May 24 '16 at 14:33
  • $\begingroup$ Is "expect" here a mathematical term or just an English word? I go for the first and confirm this. It would serve better if a tag like "probability" was used by the OP. It is questionable whether he/she is familiar with concepts like expectation. $\endgroup$ – drhab May 25 '16 at 7:15
  • $\begingroup$ @drhab: Hmmmm... That's probably why I wrote the comment above. I guess it's an English word. A similar problem lies in my usage of "the direct approach". I wasn't really sure how to describe it mathematically to be honest. $\endgroup$ – barak manos May 25 '16 at 7:19
  • $\begingroup$ You could do it with $X=X_1+\cdots+X_n$ and applying linearity of expectation. $\endgroup$ – drhab May 25 '16 at 7:20
  • 1
    $\begingroup$ Very welcome. If you meet sortlike mistakes of me then you know what to do ;-) $\endgroup$ – drhab May 25 '16 at 7:21
2
$\begingroup$

It is the expected value of $B(n,\frac{1}{3})$, where $B(n,p)$ is a binomial distribution with parameters $n\in \mathbb{N}$ and $p\in [0,1]$. Let $X\sim B(n,\frac{1}{3})$, then $$ \sum_{k=0}^n k \binom{n}{k}\left(\frac{2}{3}\right)^{n-k}\left(\frac{1}{3}\right)^{k} = E[X]= \frac{n}{3}. $$

$\endgroup$
  • $\begingroup$ Most elegant solution so far. Nice. $\endgroup$ – yurnero May 24 '16 at 14:13
  • 3
    $\begingroup$ Except that OP might be trying to prove precisely this fact. :) $\endgroup$ – kccu May 24 '16 at 14:31

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.