Consider this problem:

Let $A_1, A_2,...$ be an arbitrary finite sequence of events. Let $B_1, B_2,...$ be another finite sequence of events defined as follows: $B_1 = A_1, B_2 = A^c_1 >\cap A_2, B_3 = A^c_1 \cap A^c_2 \cap A_3,.. $

Prove: $P(\bigcup^n_{i=1} A_i) = \sum^n_{i=1}P(B_i)$

Proof using Induction:

For $\mathbf{n=1}$ $$P(\bigcup^1_{i=1} A_i) = P(A_1) \ \text{and} \ \sum^1_{i=1}P(B_i) = P(B_1) $$ $$ \text{Given} \ A_1 = B_1 \ \text{it follows that} \ P(A_1) = P(B_1)$$

Inductive step:
Assumption: $$\forall n \in N \ | \ P(\bigcup^n_{i=1} A_i) = \sum^n_{i=1}P(B_i)$$ prove that: $$P(\bigcup^{n+1}_{i=1} A_i) = \sum^{n+1}_{i=1}P(B_i)$$

Prove: $$P(\bigcup^{n+1}_{i=1} A_i)$$ $$ \iff P(\bigcup^{n}_{i=1} A_i \cup A_{n+1})$$ $$\iff P(\bigcup^{n}_{i=1} A_i) + P(A_{n+1}) - P(\bigcup^{n}_{i=1} A_i \cap A_{n+1})$$

$$ \iff P(\bigcup^{n}_{i=1} A_i) + P(A_{n+1} \cap (\bigcup_{i=1}^n A_1)^c)$$

Applying De Morgan Law

$$\iff P(\bigcup^{n}_{i=1} A_i) + P(A_{n+1} \cap (\bigcap_{i=1}^n A_1^c))$$

Due to preexistence of $B_n = \bigcap_{i=1}^{n-1} A_i^c \cap A_{n} \ \text{for} \ n > 1 $ and therefore $B_{n+1} = \bigcap_{i=1}^n A_i^c \cap A_{n+1} $ it follows that

$$ \iff P(\bigcup^{n}_{i=1} A_i) + P(B_{n+1})$$

Employing our inductive assumption for $\forall n \in N$ it follows:

$$\iff \sum^n_{i=1} P(B_i) + P(B_{n+1}) \iff \sum^{n+1}_{i=1} B_i$$

The proof at some stages does make sense in my head. Could someone please tell me whether those steps are consistent?
Thank you.


1 Answer 1


You're on the right track,

When you assume the induction hypothesis, you assume that there is some $n$ that satisfies the property $P$. You say $\forall n$, but it should be $\exists n$. Because you're ultimately proving that it's true for all $n$. Until you do that, assume it's true for some $n$.

Next, your use of $\iff$ is wrong, I assume you mean equality. You use $\iff$ to connect sentences, but you are comparing numbers, not sentences.

When you say "pre-existence of $B_n$", I'm not sure what you mean. Of course $B_n$ exists, otherwise there's nothing to prove. You probably mean "because we assumed the induction hypothesis".

If the symbols $\forall, \exists, \iff$ etc confuse you, it's okay to use natural language.

  • $\begingroup$ Thanks! Basically I summed up this statement "...B2=notA1 ∩ A2, B3=notA1 ∩ notA2 ∩ A3...." to "pre-existence of Bn equal to intersection of all notAi and An". But you are right, it's confusing. I should have used natural language $\endgroup$
    – blockR
    Jan 23, 2015 at 8:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .