Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While writing a (non-math) paper I came across the following apparent identity:

$N \cdot \mathop \sum \limits_{i = 1}^N \frac{1}{i}\left( {\begin{array}{*{20}{c}} {N - 1}\\ {i - 1} \end{array}} \right){p^{i - 1}}{\left( {1 - p} \right)^{N - i}} = \frac{{1 - {{\left( {1 - p} \right)}^N}}}{p}$

where $N$ is a positive integer and $p$ is a nonzero probability. Based on intuition and some manual checks, this looks like it should be true for all such $N$ and $p$. I can't prove this, and being mostly ignorant about math, I don't know how to learn what I need to prove this. I'd really appreciate anything helpful, whether a quick pointer in the right direction or the whole proof (or a proof or example that the two aren't identical).


Note also that ${1 - {\left( {1 - p} \right)}^N} = {{\sum\limits_{i = 1}^N {\left( {\begin{array}{*{20}{c}} N\\ i \end{array}} \right){p^i}{{\left( {1 - p} \right)}^{N - i}}} }}$

and that ${p = {1 - {\left( {1 - p} \right)}^1}}$

For background, see the current draft with relevant highlightings here.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Some manipulation gives the desired result. Mostly, one has to note that $$\frac{N}{i}\binom{N-1}{i-1}=\binom{N}{i}.$$ For $\binom{N-1}{i-1}=\frac{(N-1)!}{(i-1)!((N-1)-(i-1))!}=\frac{(N-1)!}{(i-1)!(N-i)!}.$ Multiply the top by $N$, the bottom by $i$, and we get $\frac{N!}{i!(N-i)!}$, which is just $\binom{N}{i}$.

So our sum is $$\sum_{i=1}^N\binom{N}{i}p^{i-1}(1-p)^{N-i}.$$ Multiply the inside by $p$, and divide by $p$ on the outside. We get $$\frac{1}{p}\sum_{i=1}^Np^i(1-p)^{N-i}.$$ You have written down enough facts to take it the rest of the way. Our expression is equal to $$\frac{1}{p}\left(\sum_{i=0}^N\binom{N}{i}p^i(1-p)^{N-i} -\binom{N}{0}p^0(1-p)^N \right).$$

The $\sum_{i=0}^N$ stuff is just the binomial expansion of $(p+(1-p))^N$, so it is equal to $1$. Or alternately it is the sum of the binomial probabilities, so it is $1$. Finally, the term $\binom{N}{0}p^0(1-p)^N$ is an awkward way of writing $(1-p)^N$.

share|improve this answer
    
Thank you very much, this makes perfect sense. Can I include you in the acknowledgments if/when the paper is published? –  Alex Schell Jul 28 '12 at 5:03
1  
@AlexSchell: It seems unreasonable, the result is essentially immediate. The calculation seems long just because I am long-winded, and wanted to fill in every little detail. To me it is like giving external credit for a long addition. Just quote the fact without proof, since you need space in your paper for serious things. –  André Nicolas Jul 28 '12 at 5:09
1  
@Alex Schell : I don't know in what context you are publishing this, but for a mathematician that reads papers, things like this would be considered "trivial math" (no offense, but if a mathematician sees a paper with a reference for this, he would probably not see the point). –  Patrick Da Silva Jul 28 '12 at 6:52
add comment

$$ \begin{align} N\sum_{i=1}^N\dfrac1i\binom{N-1}{i-1}p^{i-1}(1-p)^{N-i} &=\frac{(1-p)^N}{p}\sum_{i=1}^N\binom{N}{i}\left(\frac{p}{1-p}\right)^i\tag{1}\\ &=\frac{(1-p)^N}{p}\left[\left(1+\frac{p}{1-p}\right)^N-1\right]\tag{2}\\ &=\frac{(1-p)^N}{p}\left[\frac1{(1-p)^N}-1\right]\tag{3}\\ &=\frac{1-(1-p)^N}{p}\tag{4} \end{align} $$ Explanation of steps:

  1. $\displaystyle\frac{N}{i}\binom{N-1}{i-1}=\binom{N}{i}$

  2. $\displaystyle\sum_{i=0}^N\binom{N}{i}x^i=(1+x)^N\quad\quad$($i=0$ is missing, so we subtract $1$)

  3. $1+\dfrac{p}{1-p}=\dfrac1{1-p}$

  4. distribute multiplication over subtraction

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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