How to prove the two identities

Question

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.$$

2. 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!

Answer 1

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.