Is it true that $\sum_{k=1}^n(p_k\prod_{i=1}^k(1-p_i)) \stackrel{\mbox{?}}{=} 1 - \prod_{i=1}^n(1-p_i)$ Prove that
$$
p_1 + \sum_{k=2}^n \left(p_k\prod_{i=1}^{k-1}(1-p_i)\right) = 1 - \prod_{k=1}^n(1-p_k)\ . 
$$
I'm working in a code where I have to do those computations. I want to see if this equality holds in general (in order to save a lot of computation time). I tested it in practice and it seems that it is true but having the general proof would be great.
Thank you.
 A: Define, as in your second equation,
$$a_n=p_1 + \sum_{k=2}^n \left(p_k\prod_{i=1}^{k-1}(1-p_i)\right) \text{ and } b_n=1 - \prod_{k=1}^n(1-p_k)$$
Then
$$a_{n+1}-a_n=p_{n+1}\prod_{i=1}^n(1-p_i)=\left(1-\prod_{k=1}^{n+1}(1-p_k)\right)-\left(1-\prod_{k=1}^n(1-p_k)\right)=b_{n+1}-b_n.$$
With the fact that $a_1=b_1$, we must have $a_n=b_n$ for all $n$ by induction. This shows the equality holds regardless of what values the $p_i$ take on: it's just a generic telescoping reformulation.
A: Take $A_1,\ldots A_n$ $n$ independent events with $P(A_i)=p_i$. Then 
$$p_1+\sum_{k=2}^np_k\prod_{i=1}^{k-1}(1-p_i)=P(A_1)+\sum_{k=2}^nP(A_k)P\left(\bigcap_{i=1}^{k-1}A_i^c\right)=P\left(\bigcup_{k=1}^nA_k\right)$$
since it's a disjoint union and 
$$1-\prod_{k=1}^n(1-p_k)=1-\prod_{k=1}^nP(A_k^c)=1-P\left(\bigcap_{k=1}^nA_k^c\right)=P\left(\left(\bigcap_{k=1}^nA_k^c\right)^c\right)=P\left(\bigcup_{k=1}^nA_k\right).$$
Note that we didn't use the fact that $\sum_{j=1}^np_i=1$.
A: A probabilistic interpretation (perhaps easier to understand as compared to Davide's answer).
You have $n$ coins, coin $i$ has probability $p_i$ of showing heads.
Now you toss coin 1, coin 2, coin 3 in order, till you get a heads, in which case you stop.
The probability that you get heads is
$$p_1 + p_2(1-p_1) + p_3(1-p_1)(1-p_2) + \dots + p_n(1-p_1)\dots(1-p_{n-1})$$
This is same as the probability of not having all tails which is
$$ 1 - (1-p_1)(1-p_2)\dots(1-p_n)$$
You left hand side is the first expression and the right hand side is the second.
A: Imagine that $E_1,E_2,\dots,E_n$ are the mutually exclusive possible outcomes of an experiment, where $E_k$ occurs with probability $p_k$. You perform the experiment $n$ times in a row, getting outcomes $R_1,\dots,R_n$. Say that the $k$-th trial is a hit if $R_k=E_k$. The righthand side of your equation is the probability of getting at least one hit. The term $p_k\prod_{i=1}^{k-1}(1-p_i)$ on the lefthand side is the probability that the first hit occurs on the $k$-th trial. For distinct $k$ these possibilities are disjoint, so the sum on the left is clearly the same probability as the righthand side.
