0
$\begingroup$

on this page there is a proof of the Inclusion–exclusion principle, which goes
Let $A_1, A_2, ..., A_n$ be finite sets
let $ A_I = \cap_{i \in I} A_i$
then
$ \forall x \in \cup_{i = 1}^n A_i, \ (1 − 1_{A_1} ) ( 1 − 1_{A_2} ) ⋯ ( 1 − 1_{A_n} ) = 0 $
and
$\prod_{k=1}^n 1 - 1_{A_k} = \sum_{I \subset \{1,2,...,n\} }(-1)^{card(I)}1_{A_I} \ \ : \ \ (*)$
and then
$ \sum_{\emptyset \not= I \subset \{ 1,2,...,n\} } (-1)^{card(I)-1}1_{A_I} = 1 $
which inded, proves the principle by sum of x in $\cup_{k = 1}^nA_k$

but no matter how much I try, a cannot prove the second line (*), does anyone has an idea ?
Thank you for your time :).

$\endgroup$

1 Answer 1

0
$\begingroup$

When expanding $\prod_{k=1}^n(1-1_{A_k})$, a general term looks like $(-1)^{\mbox{card(I)}}\prod_{k\in I} 1_{A_k}$, where $I\subset\{1,2,\cdots,n\}$. Finally $\prod_{k\in I} 1_{A_k} = 1_{\cap_{k\in I}A_k}=1_{A_I}$, which completes the proof.

For the general term, first think about the simpler case $(1-b)^n$, which upon expansion has terms that will look like $1^ib^{n-i}$. You're just picking two exponents, such that they add to $n$. In the general case of $\prod_{k=1}^n(1-b_k)$, you pick an exponent for $1$, say $i$, and then you need to pick $n-i$ $b_k$'s, to give you $1^ib_{k_1}\cdots b_{k_{n-i}}$. Equivalently you're picking indices for $b$ out of $I\subset \{1,\cdots,n\}$, with $\mbox{card}(I)=n-i$. So when you sum all the terms, it's equivalent to just selecting subsets $I$ of $\{1,\cdots,n\}$.

$\endgroup$
2
  • $\begingroup$ Thank you ! Do you have the proof of your claim though? it is still not obvious to me. Anyway, your help means a lot. (Ps : I apologize if my english is inperfect, please note that it is not my mother tongue) $\endgroup$
    – NRagot
    May 30, 2018 at 23:13
  • $\begingroup$ @S.lama: see edit. $\endgroup$
    – Alex R.
    May 31, 2018 at 0:12

You must log in to answer this question.

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