# Is there an intuitive proof of the identity $\sum_{L \subset S} \prod_{x \in L} (x-1) = \prod_{x \in S} x$ from general principles?

Let $R$ be a commutative ring with unity, and let $S\subset R$ be any finite set. Then $$\sum_{L \subset S} \prod_{x \in L} (x-1) = \prod_{x \in S} x,$$ which is easy enough to show by induction.

Does this follow from any sort of general principle? Perhaps inclusion-exclusion, in some form?

• What does K refer to in this case? Mar 12, 2013 at 7:08
• Also, why is this tagged (probability)? Mar 12, 2013 at 7:08
• Apparently $K=S$ to make sense of this. Mar 12, 2013 at 7:18
• @meh I've made the correction above. It's tagged as probability because the general form of the identity reminds me of inclusion-exclusion (viewing $S$ as a collection of independent variables). Mar 12, 2013 at 7:21
• @A Walker Like this formula, inclusion-exclusion can be proved via distributivity: think about expanding $\prod_{i \in X} (1 - 1_{A_i})$. Mar 12, 2013 at 20:56

Let $S'$ be $\{x : x-1 \in S\}$, in other words we shift $S$ by one.

The equality $$\sum_{L \subset S} \prod_{x \in L} (x-1) = \prod_{x \in S} x$$

reduces to

$$\sum_{L \subset S'} \prod_{x \in L} x = \prod_{x \in S'} (x+1)$$

but this is obviously distributivity: LHS is the expanded RHS.

• Thanks a lot, now the identity doesn't confuse or surprise me anymore. +1 Mar 12, 2013 at 15:04

If $S=\emptyset$, then $L=\emptyset$ is the only subset and by convention the empty product $\prod_{x\in L} (x-1)$ equals $1$. That shows $$\tag1 \sum_{L\subseteq S}\prod_{x\in L}(x-1)=\prod_{x\in S}x$$ holds at least if $S=\emptyset$. For an induction step, let $a\in S$ be any element and let $S'=S\setminus\{a\}$. By assumption, $(1)$ holds with $S'$ in place of $S$. We find \begin{align}\sum_{L\subseteq S}\prod_{x\in L}(x-1)&=\sum_{a\in L\subseteq S}\prod_{x\in L}(x-1)+\sum_{a\notin L\subseteq S}\prod_{x\in L}(x-1)\\ &=\sum_{L\subseteq S'}(a-1)\prod_{x\in L}(x-1)+\sum_{L\subseteq S'}\prod_{x\in L}(x-1)\\ &=a\cdot\sum_{L\subseteq S'}\prod_{x\in L}(x-1)\\ &=a\cdot \prod_{x\in S'}x = \prod_{x\in S}x.\end{align}

Clearly it suffices to show the result when $R=\mathbb Z[S]$ and $S$ is the (finite) set of indeterminates of the polynomial ring $R$ (just specialize).

Let $T$ be any nonempty subset of $S$, and let $x_T=\prod_{x\in T}x$. Given $L\subseteq S$, it follows that $x_T$ appears in the expansion of $\prod_{x\in L}(x-1)$ if and only if $L\supseteq T$, and it appears precisely with coefficient $(-1)^{|L\setminus T|}$. Therefore the coefficient of $x_T$ in $\sum_{L\subseteq S}\prod_{x\in L}(x-1)$ is precisely

$$\sum_{L\supseteq T}(-1)^{|L\setminus T|}\,.$$

If $T$ is a proper subset of $S$, then you can fix an element $z$ outside $T$. From this you can see that the sets $L$ containing $T$ come in two "flavors": those of the form $T\cup Q$, with $Q\subseteq S\setminus\bigl(T\cup\{z\}\bigr)$, and those of the form $T\cup Q\cup\{z\}$, with $Q$ as before, so your coefficient is given by

$$\sum_Q\biggl[(-1)^{\bigl|\,(Q\cup\{z\})\setminus T\,\bigr|}+(-1)^{\bigl|\,Q\setminus T\,\bigr|}\biggr]=\sum_Q0=0\,.$$

Finally, the coefficient of $x_S$ is clearly equals to $(-1)^0=1$.

$$\begin{array}{cl} \sum_{L \subseteq S} \prod_{x \in L} (x-1) & = \sum_{L\subset S}\sum_{M\subseteq L}(-1)^{|L\setminus M|}\prod_{x\in M}x \\ & =\sum_{M\subseteq S}\left[\sum_{M\subseteq L\subseteq S}(-1)^{|L\setminus M|}\right]\prod_{x\in M}x \\ & = \sum_{M\subseteq S}\left[\sum_{\ell=|M|}^{|S|}{|S|-| M|\choose \ell-|M|}(-1)^{\ell-|M|}\right] \prod_{x\in M}x \\ & = \sum_{M\subseteq S}\delta_{|S|,|M|}\prod_{x\in M}x \\ & = \prod_{x\in S}x. \end{array}$$

You can notice the Möbius function of the poset of subsets of $S$ in the above, so there is definitely some combinatorial inclusion-exclusion going on here.

• Yes, if you replace $(x-1)$ with $(1-x)$ (and add a corresponding sign before the product) and then interprete $x$ as a probability, at last the relation to the probability tag becomes clearer ... Mar 12, 2013 at 7:47