3
$\begingroup$

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.

2 Answers 2

3

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$.

  • 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).2012-07-28
2

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