Let $m,n$ be positive integers and $N=\{1,\ldots, n\}$. Try to prove the two following identites:

  1. For $m<n$, we have $$\sum_{A \subseteq N} (-1)^{\left| A\right|} \left(\sum_{j \in A} x_j\right)^m = 0.$$

E.g., for $n=3, m=1$, we have $$(x_1+x_2+x_3) = (x_1+x_2) + (x_1+x_3) + (x_2+x_3) - x_1 - x_2 - x_3,$$ and for $n=3, m=2$, we have again $$(x_1+x_2+x_3)^2 = (x_1+x_2)^2 + (x_1+x_3)^2 + (x_2+x_3)^2 - x_1^2 - x_2^2 - x_3^2.$$

  1. For $m=n$, we have $$\sum_{A \subseteq N} (-1)^{\left| A\right|} \left(\sum_{j \in A} x_j\right)^n = (-1)^{n} n! \prod_{i=1}^{n}x_i.$$

E.g., for $m=n=2$, we have $$(x_1+x_2)^2 = x_1^2 + x_2^2 + 2!x_1 x_2,$$ and for $m=n=3$, we have $$(x_1+x_2+x_3)^3 = (x_1+x_2)^3 + (x_1+x_3)^3 + (x_2+x_3)^3 - x_1^3 - x_2^3 - x_3^3 + 3!x_1x_2x_3.$$

I think the both identities could be proved by mathematical induction, but I still have no idea how to prove them. Hoping to see some smart ideas. Thanks a lot!


First note that $$\sum_{A \subseteq N} (-1)^{\left| A\right|} \left(\sum_{j \in A} x_j\right)^m\tag 1$$ is an homogeneus polynomial of degree $m$ in the variables $x_1,\ldots,x_n$. Let consider a generic monomial $\prod_{i=1}^nx_i^{e_i}$ with $e_i\in\Bbb N$ and $\sum_{i=1}^ne_i=m$. Its coefficient in $(1)$ is given by $$\sum_{S\subseteq A\subseteq N}(-1)^{|A|}\frac{m!}{\prod_{i=1}^ne_i!}$$ where $S=\{i:e_i>0\}$. Moreover \begin{align} \sum_{S\subseteq A\subseteq N}(-1)^{|A|} &=(-1)^{|S|}\sum_{B\subseteq N\setminus S}(-1)^{|B|}\\ &=(-1)^{|S|}\sum_{k=0}^{|N\setminus S|}\binom{|N\setminus S|}k(-1)^k\\ &= \begin{cases} 0&S\neq N\\ (-1)^{|S|}&S=N \end{cases} \end{align}

If $m<n$ or ($m=n$ and $e_i>1$ for some $i$), then $S\neq N$, hence $(1)$ is proved to be $0$ in this case.

If $m=n$ and $e_i=1$ for all $i$, then $S=N$, hence the coefficient is $(-1)^nn!$ and this proves the second identity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.