# Proof of the inclusion-exclusion principle

The inclusion-exclusion principle for $$n$$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:

THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION   Let $$A_1,A_2,\ldots,A_n$$ be finite sets. Then $$\begin{multline*} |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|. \end{multline*}$$ Proof: We will prove the formula by showing that an element in the union is counted exactly once by the right-hand side of the equation. Suppose that $$a$$ is a member of exactly $$r$$ of the sets $$A_1,A_2,\ldots,A_n$$, where $$1 \leq r \leq n$$. This element is counted $$\binom{r}{1}$$ times by $$\sum |A_i|$$. It is counted $$\binom{r}{2}$$ times by $$\sum |A_i \cap A_j|$$. In general, it is counted $$\binom{r}{m}$$ times by the summation involving $$m$$ of the sets $$A_i$$. Thus, this element is counted exactly $$\binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}$$ times by the expression on the right-hand side of this equation. Our goal is to evaluate this quantity. The binomial formula shows that $$0 = (1-1)^r = \binom{r}{0} - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^r \binom{r}{r}.$$ Hence $$1 = \binom{r}{0} = \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}.$$ Therefore, each element in the union is counted exactly once by the expression on the right-hand side of the equation. This proves the principle of inclusion-exclusion.

Although the proof seems very exciting, I am confused because what the author has proved is $$1=1$$ from the LHS and RHS.

Thus, is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $$1$$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra summation sign should be appended before the expression in RHS. Could someone please clarify?

• Who is the author, and what textbook is this taken from? – Yuval Filmus Dec 16 '19 at 20:48
• @YuvalFilmus discrete Math, Keneth Rosen – MathMan Dec 16 '19 at 20:53

Let me slightly rephrase the argument. Let $$N_r$$ be the number of elements contained in exactly $$r$$ of the sets $$A_1,\ldots,A_n$$. Then the left-hand side is $$|A_1 \cup \cdots \cup A_n| = \sum_{r=1}^n N_r.$$ The first sum on the right-hand side is $$\sum_{1 \leq i \leq n} |A_i| = \sum_{r=1}^n \binom{r}{1} N_r.$$ The second sum on the right-hand side is $$\sum_{1 \leq i < j \leq n} |A_i \cap A_j| = \sum_{r=2}^n \binom{r}{2} N_r.$$ More generally, the $$m$$th sum on the right-hand side is $$\sum_{1 \leq i_1 < i_2 < \cdots < i_m \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_m}| = \sum_{r=m}^n \binom{r}{m} N_r.$$ Therefore the right-hand side is equal to $$\sum_{r=1}^n \binom{r}{1} N_r - \sum_{r=2}^n \binom{r}{2} N_r + \sum_{r=3}^n \binom{r}{3} N_r - \cdots + (-1)^{n+1} \sum_{r=n}^n \binom{r}{n} N_r.$$ Rearranging, the right-hand side is equal to $$\left[ \binom{1}{1} \right] N_1 + \left[ \binom{2}{1} - \binom{2}{2} \right] N_2 + \left[ \binom{3}{1} - \binom{3}{2} + \binom{3}{3} \right] N_3 + \cdots + \\ \left[ \binom{n}{1} - \binom{n}{2} + \binom{n}{3} - \cdots + (-1)^{n+1} \binom{n}{n} \right] N_n.$$ The coefficient of the general term $$N_m$$ is $$\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}.$$ By the binomial theorem, this equals $$1$$, and so the right-hand side equals $$1 \cdot N_1 + 1 \cdot N_2 + 1 \cdot N_3 + \cdots + 1 \cdot N_n = \sum_{r=1}^n N_r,$$ which is exactly the same as the left-hand side.
• Sorry. Do you mean $N_r = |A_r|?$ – MathMan Dec 16 '19 at 21:42
• I have a bit difficulty comprehending the meaning of $N_r$ here. Thanks for your efforts! – MathMan Dec 16 '19 at 21:44
• No, I don't mean $N_r = |A_r|$. Give it a few hours and see if you can decipher my definition of $N_r$. – Yuval Filmus Dec 16 '19 at 22:28
Yes, you are right that an extra summation needs to be appended to the beginning of both sides to prove the inclusion-exclusion formula. This can be understood by using indicator functions (also known as characteristic functions), as follows. Let $$U$$ be some finite set (the universe), and let $$S \subseteq U$$. The indicator function (or characteristic function) of $$S$$ is the 0,1-valued function $$I_S: U \rightarrow \{0,1\}$$ on the domain $$U$$, defined by $$I_S(x) = 1$$ if $$x \in U$$, and $$I_S(x)=0$$ if $$x \notin U$$. Observe that $$|S| = \sum_{x \in U} I_S(x)$$. In other words, the number of elements in $$S$$ is equal to a sum of $$0$$'s and $$1$$'s, where the number of $$1$$'s is of course the size of $$S$$. We are interested in the case where $$S = A_1 \cup A_2 \cup \cdots \cup A_n$$.
What the proof given in text shows is that the indicator function $$I_S$$ (where $$S = A_1 \cup A_2 \cup \cdots \cup A_n$$) is equal to a particular sum of indicator functions (where the subscripts for these latter indicator functions are intersections of the $$A_i$$'s). More specifically, it is proved that $$I_{A_1 \cup \cdots \cup A_n} = (I_{A_1} + \cdots + I_{A_n} ) - (I_{A_1 \cap A_2} + \cdots + \cdots I_{A_{n-1} \cap A_n}) + (I_{A_1 \cap A_2 \cap A_3} + \cdots )+ \cdots + (-1)^n I_{A_1 \cap \cdots \cap A_n}.$$ This formula holds because, as you show, if an element $$x \in U$$ appears in exactly $$r$$ of the $$A_i$$'s for some $$r \ge 1$$, then the LHS indicator function trivially evaluates to $$1$$, and the RHS sum of indicator functions also evaluates to $$1$$ (by the binomial formula). Similarly, both sides evaluate to $$0$$ if $$r=0$$ (i.e. if $$x \in U, x \notin S$$). Thus, the two 0,1-valued functions are equal, meaning the two functions take the same value for each $$x$$ in the domain $$U$$. This means the many terms in RHS sum cancel out to give either a $$0$$ or a $$1$$, for any $$x \in U$$ that you pick.
If two functions $$f, g$$ on domain $$U$$ are equal, i.e. if $$f(x)=g(x)$$ for all $$x \in U$$, then the summations $$\sum_{x \in U} f(x)$$ and $$\sum_{x \in U} g(x)$$ are also equal. So, take the summation of the LHS indicator function's values over $$x \in U$$, and similarly for the RHS. Recall that for any set $$X \subseteq U$$, we have $$\sum_{x \in U} I_X(u) = |X|$$. So, for the left hand side, the sum $$\sum_{x \in U} I_{A_1 \cup \cdots \cup A_n}(x)$$ evaluates to $$|A_1 \cup \cdots \cup A_n|$$. For the right hand side, we are taking the sum of all those indicator functions over $$x \in U$$. Use the fact that $$\sum_{x \in U} I_{A_i}(x) = |A_i|$$, that $$\sum_{x \in U} I_{A_1 \cap A_2}(x) = |A_1 \cap A_2|$$ (by taking $$X = A_1 \cap A_2$$), and so on, to get the inclusion-exclusion formula.