Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Inclusion-exclusion principle was formulated in my school in this way:

Let $A_i,\ldots,A_n \subseteq X$, where $X$ is a finite set. Let

$$S_r=\displaystyle \sum_{1 \le i_1< \cdots < i_r \le n} |A_{i_1}\cap \cdots \cap A_{i_r}|,\text{ and }S_0=|X|.$$

If $D(k)$ is number of elements belonging to exactly $k$ sets (from $A_i,\ldots,A_n$), then we have: $D(k)=\sum_{r\ge k}{r\choose k}(-1)^{r-k}S_r$.

Now the task is:

Prove that if $\displaystyle A(r)=\sum_{j=r+1}^n (-1)^jS_j$ then $A(r)\le 0$ when $r$ is even and $A(r)\ge 0$ when $r$ is odd.

Is it even true? It's difficult to imagine, let alone solve it. I don't even know how to start, can anybody help?

share|improve this question
Is this the same as math.stackexchange.com/questions/124043/…? –  Gerry Myerson Mar 29 '12 at 6:11
link doesn't work.. –  xan Mar 29 '12 at 16:38
Yes, OP deleted that post so you can't see it. I have voted to undelete it. But ... you made a comment on that post, so you have seen it. Anyway, I made a reference to the Bonferroni inequalities, maybe that will help you. –  Gerry Myerson Mar 30 '12 at 1:30
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.