An inequality $||x_1+\dots+x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||$. 
Let $X$ be a Banach space, $x_1,...,x_n\in X$. I want to know if the following is true or not:
  $$
||x_1+\dots+x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||,
$$
  where the average is taken over all possible assignment of $2^n$ plus/minus signs.

For $n=1$ this is trivial. For $n=2$ we have
$$\begin{align}
||x+y|| &= \frac12\left(||+x+y||+||-x-y|| \right) \\
&\le 2\cdot\frac14\left(||+x+y||+||-x-y||+||+x-y||+||-x+y|| \right)
\end{align}$$
which is simple enough since there are $2$ superficial terms on the RHS. However, for $n=3$ we need all the terms
$$\begin{align}
||x+y+z|| &= ||+x+y+z|| \\
||x+y+z|| &= ||-x-y-z|| \\
||x+y+z|| &\le ||+x+y-z|| +||+x-y+z|| +||-x+y+z|| \\
||x+y+z|| &\le ||-x-y+z|| +||-x+y-z|| +||+x-y-z|| \\
\end{align}$$
summing over the LHS and RHS gives the result.
From this observation, it'd seem that math induction might not be the way to go. So how should we prove/disprove the inequality here?

Remark: Since the RHS is symmetric in plus/minus signs, the inequality in question actually implies something stronger(if it is true) namely
  $$
\text{max}||\pm x_1\pm\dots\pm x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||.
$$

 A: The inequality is false for $n=4$. Let's consider the well-studied Banach space $\mathbb R$ and take $x_1 = x_2 = x_3 = x_4 = 1$. The average value of $|\pm1 \pm1 \pm1 \pm1|$ is $$\frac1{16}\left(\binom40 \cdot 4 + \binom41 \cdot 2 + \binom42 \cdot 0 + \binom43 \cdot2 + \binom44 \cdot 4\right) = \frac{24}{16} = \frac32,$$ but the maximum value is $4$. 
A: Let $X$ be any Banach space. Let $x_1\in X$ with $\|x_1\|=1$, and put $x_j=x_1\ne0$ for all $j$. Then 
$$
\|x_1+\cdots+x_n\|=n. 
$$
On the other hand,
$$
\|\pm x_1\pm   \cdots\pm x_n\|=|p-m|=|n-2p|,
$$
where $p,m$ are respectively the number of plus and minus signs. For each choice of $p$, there are $n\choose p$ possible orderings. So the right-hand-side in your inequality is 
$$
\frac2{2^n}\,\sum_{p=0}^n {n\choose p}\,|n-2p|.
$$
For simplicity, let us assume $n$ is even, i.e., $n=2k$. Then 
\begin{align}
\frac2{4^k}\,\sum_{p=0}^{2k} {2k\choose p}\,|2k-2p|
&=\frac1{4^{k-1}}\,\sum_{p=0}^{2k} {2k\choose p}\,|k-p|\\ \ \\
&=\frac1{4^{k-1}}\,\left(\sum_{p=0}^{k-1} {2k\choose p}\,(k-p)+\sum_{p=k+1}^{2k} {2k\choose p}\,(p-k)\right)\\ \ \\
&=\frac1{4^{k-1}}\,\left(\frac k2\,{2k\choose k} +\frac{k+1}2\,{2k\choose k+1}\right)
\end{align}
So your inequality would be (cancelling a 2 on each side)
$$
k\leq \frac1{4^{k-1}}\,\left(\frac k2\,{2k\choose k} +\frac{k+1}2\,{2k\choose k+1}\right),
$$
that is
$$
1\leq \frac1{4^{k-1}}\,\left(\frac 12\,{2k\choose k} +\frac{k+1}{2k}\,{2k\choose k+1}\right).
$$
But already for $k=5$ the expression on the right is less than $1$ (and goes to zero as $k\to\infty)$. 
