Prove a polynomial identity of $n$ variables

Question

For integer $n\ge3$, let $A=x_1+x_2+\cdots +x_n$, define $S_n(k)$:

• $S_n(0)=A^n$
• for $0<k\le n$, $\displaystyle S_n(k)=\sum_{\{i_1,i_2,\ldots,i_k\}\subseteq\{1,2,\ldots,n\}}\bigl(A-2(x_{i_1}+x_ {i_2}+\cdots+x_{i_k})\bigr)^n$
  where $\{i_1,i_2,\ldots,i_k\}$ are distinct.

@kuing conjectured that $$ S_n(0)-S_n(1)+S_n(2)-S_n(3)+\cdots+(-1)^nS_n(n)=2^nn!\cdot x_1x_2\cdots x_n, $$ When $n=3$, let $(x_1,x_2,x_3)=(a,b,c)$, then \begin{align} S_3(0)&=(a+b+c)^3,\\ S_3(1)&=(-a+b+c)^3+(a-b+c)^3+(a+b-c)^3,\\ S_3(2)&=(-a-b+c)^3+(-a+b-c)^3+(a-b-c)^3,\\ S_3(3)&=(-a-b-c)^3, \end{align} We have $$ S_3(0)-S_3(1)+S_3(2)-S_3(3)=48abc. $$ When $n=4$, let $(x_1,x_2,x_3,x_4)=(a,b,c,d)$, then \begin{align} S_4(0)={}&(a+b+c+d)^4,\cr S_4(1)={}&(-a+b+c+d)^4+(a-b+c+d)^4+(a+b-c+d)^4+(a+b+c-d)^4,\cr S_4(2)={}&2[(-a-b+c+d)^4+(-a+b-c+d)^4+(-a+b+c-d)^4],\cr S_4(3)={}&(-a-b-c+d)^4+(a-b-c-d)^4+(-a-b+c-d)^4+(-a+b-c-d)^4\cr S_4(4)={}&(-a-b-c-d)^4, \end{align} We have $$ S_4(0)-S_4(1)+S_4(2)-S_4(3)+S_4(4) =384abcd. $$ The identity for $n=3$ is easy to prove:

The expression is of degree $3$, and vanishes when $a=0$: each term with $a$ cancels the term with $-a$ on the next line: \begin{array}{l} S_3(0)&=(a+b+c)^3\cr S_3(1)&=(-a+b+c)^3&+(a-b+c)^3&+(a+b-c)^3\cr S_3(2)&=&+(-a-b+c)^3&+(-a+b-c)^3&+(a-b-c)^3\cr S_3(3)&=&&&+(-a-b-c)^3 \end{array} By symmetry it also vanishes when $b=0,c=0$, and therefore must be equal to $Cabc$.

---

The identity for $n=4$ can be proved using the same method: each term with $a$ cancels the term with $-a$ on the next line: \begin{array}{l} S_4(0)={}&(a+b+c+d)^4\cr S_4(1)={}&(-a+b+c+d)^4&+(a-b+c+d)^4&+(a+b-c+d)^4&+(a+b+c-d)^4\cr S_4(2)={}&&(-a-b+c+d)^4&+(-a+b-c+d)^4&+(-a+b+c-d)^4\cr &&+(a+b-c-d)^4&+(a-b+c-d)^4&+(a-b-c+d)^4\cr S_4(3)={}&(a-b-c-d)^4&+(-a+b-c-d)^4&+(-a-b+c-d)^4&+(-a-b-c+d)^4\cr S_4(4)={}&(-a-b-c-d)^4 \end{array} Do you think this method can be generalized to prove the identity for all $n\ge3$?

---

Also, taking $x_1=\dots=x_n=1$ we get $$2^nn!=\sum _{k=0}^n (-1)^k (n-2 k)^n \binom{n}{k}$$

Answer 1

A natural extension of your method, with some extra notation, can be used to prove the identity.

Let $G$ denote the set of $\{-1,1\}$-sequences of length $n$, and let $t(s)$ denote the number of $-1$s in $s$. Then $$S_n(k)=\sum_{\substack{s\in G_n\\t(s)=k}}(s\cdot x)^n;$$ this gives $$S_n(0)-S_n(1)+\cdots+(-1)^nS_n(n)=\sum_{s\in G}(-1)^{t(s)}(s\cdot x)^n.$$ Given a polynomial $f$ of degree at most $n$, let $$c_n(f;x_1,\dots,x_n)=\sum_{s\in G_n}(-1)^{t(s)}f(s\cdot x).$$ We claim that $$c_n(f)=2^nn!\cdot(\text{degree-$n$ coefficient of $f$})\cdot(x_1\cdots x_n),$$ in line with the conjectures of the main post. The base case of $n=0$ follows from the easy computation $c_0(f)=1$.

---

To show this, we use induction on $n$. We have, letting $y=(x_1,\dots,x_{n-1})$, that $$c_n(f;x_1,\dots,x_n)=\sum_{s\in G_{n-1}}(-1)^{t(s)}\big(f(s\cdot y+x_n)-f(s\cdot y-x_n)\big);$$ letting $f_{x_n}$ be defined so that $f_{x_n}(u)=f(u+x_n)-f(u-x_n)$, this shows $$c_n(f;x_1,\dots,x_n)=c_{n-1}(f_{x_n},x_1,\dots,x_{n-1}).$$ This lets us reduce the number of variables and the degree of the polynomial considered. Since $f_{x_n}$ has degree at most $\deg f-1\leq n-1$, our inductive hypothesis implies $$c_n(f;x_1,\dots,x_n)=2^{n-1}(n-1)!\cdot(\text{degree $n-1$ coefficient of $f_{x_n}$})\cdot x_1\cdots x_{n-1}.$$ Let $f(u)=a_nu^n+a_{n-1}u^{n-1}+\cdots$; then \begin{align*} f_{x_n}(u) &=f(u+x_n)-f(u-x_n)\\ &=a_n\big((u+x_n)^n-(u-x_n)^n\big)+a_{n-1}\big((u+x_n)^{n-1}-(u-x_n)^{n-1}\big)+\cdots\\ &=a_n\big(2nx_nu^{n-1}+\cdots\big)+a_{n-1}\big(2(n-1)x_nu^{n-2}+\cdots\big) \end{align*} has degree $n-1$ coefficient $2nx_na_n$. This allows us to complete our induction, as desired.

Answer 2

Let us calculate directly (without induction) this sum $$A:=\sum_{k=0}^n(-1)^kS_n(k).$$ Rewriting it as $$A=\sum_{\varepsilon\in\{-1,1\}^n}\left(\sum_{i=1}^n\varepsilon_ix_i\right)^n\prod_{i=1}^n\varepsilon_i$$ and developing each $\left(\sum_{i=1}^n\varepsilon_ix_i\right)^n,$ we soon realize that all monomials where at least one of the $x_i$'s is raised to a power $>1$ cancel mutually.

There only remains $$A=\sum_{\varepsilon\in\{-1,1\}^n}n!\prod_{i=1}^n(\varepsilon_ix_i)\prod_{i=1}^n\varepsilon_i= 2^nn!\prod_{i=1}^nx_i.$$

Answer 3

In general, suppose you have an ordinary generating function in $n$ variables, $$ f(x_1,\dots,x_n) =\sum_{i_1,\dots,i_n\ge 0}a_{i_1,\dots,i_n}\,x_1^{i_1}\cdots x^{i_n}_n , $$ where for each $n$-tuple of nonnegative integers $(i_1,\dots,i_n)$, $a_{i_1,\dots,i_n}$ is a real number. I claim the following: $$ 2^{-n}\newcommand{\e}{\varepsilon}\sum_{\varepsilon\in \{-1,1\}^n} \e_1\cdots \e_n\cdot f(\e_1x_1,\dots,\epsilon_nx_n) =\sum_{i_1,\dots,i_n\ge 0}a_{2i_1+1,\dots,2i_n+1}\; x_1^{2i_1+1}\cdots x_{n}^{2i_n+1}\tag1 $$ That is, if you take the alternating sum of $f(\pm x_1,\dots,\pm x_n)$ over all $2^n$ ways to choose the signs for the input variables, where the sign of each summand is $+1$ if there are an even number of negated $x_i$'s and $-1$ otherwise, and divide by $2^n$, then the result is a new generating function where the coefficient of any monomial with an even power of some variable is zero, but the coefficients of monomials where all powers are odd are unchanged.

This may seem complicated, but it is a natural generalization of the following identity for single-variable generating functions, which is a bit more obvious: $$ f(x)=\sum_{i\ge 0}a_ix^i\implies \frac{f(x)-f(-x)}{2}=\sum_{i\ge 0} a_{2i+1}\;x^{2i+1} $$ When $n=2$, $(1)$ is saying that $$ f(x,y)=\sum_{i,j\ge 0}a_{i,j}x^iy^j\implies \frac{f(x,y)-f(x,-y)-f(-x,y)+f(-x,-y)}{4}=\sum_{i,j\ge 0} a_{2i+1,2j+1} x^{2i+1}y^{2j+1} $$ To prove $(1)$, for each $i\in \{1,\dots,n\}$, define the operator $O_i$ on $n$-variable functions by $$O_i [f(x_1,\dots, x_n)]=\frac{f(x_1,\dots,x_n)-f(x_1,\dots,x_{i-1},-x_i,x_{i+1}\dots,x_n)}{2}.$$ That is, $O_i[f]$ is the difference between $f$, and the modified $f$ where the $i^\text{th}$ variable is negated, divided by $2$.

It should be clear by analyzing the power series that $O_i[f]$ has the same coefficients of $f$, except that all monomials with an even power of $x_i$ have their coefficient changed to zero. Therefore, $(O_1\circ O_2\circ \dots \circ O_n)[f]$ matches the right-hand-side of $(1)$. But it is easy to see directly, or by induction, that applying all the operators $O_1,\dots,O_n$ to $f$ results in the LHS of $(1)$.

---

To apply this to your problem, we let $$ f(x_1,\dots,x_n) =(x_1+\dots+x_n)^n =\sum_{\substack{i_1,\dots,i_n\ge 0 \\ i_1+\dots+i_n=n}} \binom{n}{i_1,\dots,i_n}x_1^{i_1}\cdots x_n^{i_n}\tag2 $$ Note that $S_n(0)-S_n(1)+\dots+(-1)^nS_n(n)$ is exactly equal to $\sum_{\varepsilon\in \{-1,1\}^n} \e_1\cdots \e_n\cdot f(\e_1x_1,\dots,\epsilon_nx_n)$. Using $(1)$, this is equal to $2^n$ times the result of taking the RHS of $(2)$, and zeroing out any coefficient where some exponent of $x$ is even. But the only monomial in the summation of $(2)$ where all coefficients are odd is exactly $x_1x_2\cdots x_n$, which comes with coefficient $\binom{n}{1,\dots,1}=n!$. This proves that $S_n(0)-S_n(1)+\dots+(-1)^nS_n(n)=2^nn!\cdot x_1\dots x_n$, as desired.