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

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.

StackExchange Computer Science Q#118597, answer score: 5