1. ## Inclusion-Exclusion Principle Proof

Inductive Step
Assume true for n so lA_1U.....UA_nl = lA_1l +....+ lA_nl - lA_1nA_2l +lA_1nA_2nA_3l -........+ (-1)^n-1lA_1n....nA_nl

Now aim to prove true for n+1
so we take finite sets A_1,.....,A_n,A_n+1

lA_1U...UA_nUA_n+1l= lA_1U....UA_nl + lA_n+1l - l(A_1U....UA_n)nA_n+1l

How do u use the inductive step to prove for n+1?

2. Originally Posted by qwerty10
Inductive Step
Assume true for n so lA_1U.....UA_nl = lA_1l +....+ lA_nl - lA_1nA_2l +lA_1nA_2nA_3l -........+ (-1)^n-1lA_1n....nA_nl

Now aim to prove true for n+1
so we take finite sets A_1,.....,A_n,A_n+1

lA_1U...UA_nUA_n+1l= lA_1U....UA_nl + lA_n+1l - l(A_1U....UA_n)nA_n+1l
How do u use the inductive step to prove for n+1?
The greatest drawback is notation. Here is one suggestion.
$\left| {A_1 \cup A_2 \cup \cdots A_n } \right| = \sum\limits_j {\left| {A_j } \right|} - \sum\limits_{j < k} {\left| {A_j \cap A_k } \right|} + \sum\limits_{j < k < n} {\left| {A_j \cap A_k \cap A_n } \right|} \cdots ( - 1)^n \sum\limits_j {\left| {A_1 \cap A_2 \cap \cdots A_n } \right|}$