# Inclusion-Exclusion principle and finite product identity

On this page, there is a proof that uses the inclusion-exclusion principle to provide a formula for the value of Euler's totient function. I would be grateful if someone could explain the reasoning behind the final step, namely: \begin{aligned} n \left(1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_i p_j} -\sum \frac{1}{p_i p_j p_k} + \cdots + (-1)^{|P|} \frac{1}{p_1 p_2 \cdots p } \right) \ &= n \prod_{p \in P} \left(1-\frac{1}{p}\right) \end{aligned} The author states that the final step relies on the following identity: \begin{aligned} \prod_{i=1}^n (1 - x_i) &= 1 - \sum x_i + \sum x_i x_j - \sum x_i x_j x_k + \cdots + (-1)^n x_1 x_2 \cdots x_n \\ & = \sum_{I \subset {1, 2, \ldots, n}} (-1)^{|I|}\prod_{i \in I} x_i \end{aligned}

I am aware of other proofs of Euler's phi function which rely on first proving that it is a multiplicative function. I'm not interested in that aspect. The author of the first link explicitly states his preference for a method that does not require it. I'm interested in how one proceeds from the inclusion-exclusion expression to the product. Is it simply from the binomial expansion of the product?

Thanks

CL

Consider the product $(1-x_1)(1-x_2) \cdots (1-x_n)$. When you expand it out, you get $1 - x_1 - x_2 \cdots - x_n + x_1 x_2 + x_1 x_3 + \cdots + (-1)^n x_1 \cdots x_n$. Observe that each term in the resulting expansion is actually a product of $n$ terms, each of which is either equal to $1$ or $-x_i$ for some $i$. For example, the term $x_3 x_5$ in the expansion is really obtained due to the product $(1)(1)(-x_3)(1)(-x_5)(1) \cdots (1)$. This term can be expressed in the form $(-1)^{|I|} \Pi_{i \in I} x_i$, where $I = \{3,5\}$. Of course, $I$ can be any subset of $\{1,2,\ldots,n\}$, and so you obtain the general formula above.