# sum of Problem from Olympiad from book

This following problem from book,I don't understand this part. The book never explains how to get from a word to a point. $$\sum_{\xi_{1},\xi_{2},\cdots,\xi_{n}\in\{-1,1\}}\left(\sum_{i=1}^{n}\xi_{i}x_{i}\right)^2=2^n\sum_{i=1}^{n}x^2_{i}$$ Thanks

Fix $\xi_1, \xi_2, \dots, \xi_n$

If $\xi_i$ and $\xi_j$ have the same sign, then in

$$\left(\displaystyle\sum_{i=1}^{n} \xi_i x_i\right)^2$$

we have a term $2x_ix_j$

If $\xi_i$ and $\xi_j$ have opposite signs, we get a term $-2x_ix_j$

But $\xi_i$ and $\xi_j$ have opposite signs half the time and the same sign half the time, so when we sum over all values of $\xi_1, \xi_2, \dots, \xi_n$, these cross-terms all cancel out.

So what we are left with are only the terms involving $x_i^2$, and there are exactly $2^n$ of these, giving the result.

Here is a probabilistic proof. Let $\kappa_1,\dots,\kappa_n$ be independent symmetric Bernoulli variables (i.e. $P(\kappa_i = 1) = P(\kappa_i = -1)= 1/2$). Then $$\mathrm{E}\left(\sum_{k=1}^n x_k\kappa_k\right)^2 = \mathrm{Var}\left(\sum_{k=1}^n x_k\kappa_k\right) = \sum_{k=1}^n \mathrm{Var}(x_k\kappa_k) = \sum_{k=1}^n x_k^2,$$ where in the first equality we have used that $\mathrm{E}\kappa_k = 0$, $k=1,\dots,n$.

Rewriting the expectation in terms of joint distribution, $$\sum_{k=1}^n x_k^2 = \mathrm{E}\left(\sum_{k=1}^n x_k\kappa_k\right)^2 = \sum_{\xi_{1},\xi_{2},\cdots,\xi_{n}\in\{-1,1\}}\left(\sum_{i=1}^{n}\xi_{i}x_{i}\right)^2\mathrm{P}\left(\kappa_1=\xi_1,\dots,\kappa_n = \xi_n\right) \\ = 2^{-n} \left(\sum_{i=1}^{n}\xi_{i}x_{i}\right)^2,$$ as required.

For example, for $n=3$, the sum is $$(x+y+z)^2+(x+y-z)^2+(x-y+z)^2+(x-y-z)^2\\+(-x+y+z)^2+(-x+y-z)^2+(-x-y+z)^2+(-x-y-z)^2\\=8(x^2+y^2+z^2)$$

It is clear to understand that the coefficient of the $x_i^2$ terms since the $\xi_i^2 = 1$ all the time. So the point is to understand why the $x_ix_j$ terms go off.

Fix a pair $i \neq j$, lets find out the exact coefficient of each time that the term $x_i x_j$ that appears in the sum. Since all the other indices $\xi_k,\,\,k \neq i ,j$ can be $-1$ or $1$, so each of the 4 possible choice of $(\xi_i, \xi_j)$ appears $2^{n-2}$ times.

So there are $2^{n-2}$ terms with $\xi_i = 1, \xi_j = 1$, $2^{n-2}$ terms with $\xi_i = 1, \xi_j = -1$, $2^{n-2}$ terms with $\xi_i = -1, \xi_j = 1$ and $2^{n-2}$ terms with $\xi_i = -1, \xi_j = -1$, so in the total sum the coefficient of the term $x_i x_j$ is :

\begin{align} & 1 \times 1 \times 2^{n-2} + 1 \times (-1) \times 2^{n-2} + (-1) \times 1 \times 2^{n-2} + (-1) \times (-1) \times 2^{n-2} \\ &= 2^{n-2} \times (1- 1 - 1 + 1) \\ &= 0. \end{align}

That is why $\forall \,i \neq j$, the $x_i x_j$ term disappears in the total sum.