3
$\begingroup$

I have been trying to prove the following inequality. Let $[n] = \{1, \dots, n\}$, and let $\mathcal{S} = \{S \subseteq [n] : |S| = n-1\}$. Then, for all $0 \leq x_1, \dots, x_n \leq 1$: $$\sum_{S \in \mathcal{S}} \prod_{j \in S} x_j \leq 1 + n\prod_{j \in [n]} x_j$$ For example, when we set $n = 2$, we obtain the following inequality: $$x_1 + x_2 \leq 1 + 2x_1x_2 \qquad (0 \leq x_1,x_2 \leq 1)$$ And for $n = 3$, the inequality becomes: $$x_1x_2 + x_1x_3 + x_2x_3 \leq 1 + 3x_1x_2x_3 \qquad (0 \leq x_1,x_2,x_3 \leq 1)$$ Any hints on how to prove these inequalities for general $n \in \mathbb{N}$ would be greatly appreciated.

Note: Equality only occurs when all variables $x_1, \dots, x_n$ equal $1$, except for one, which equals $0$. So, for $n = 2$, equality occurs for $(0,1)$ and $(1,0)$, and for $n = 3$, we obtain equality when we take $(0,1,1)$, $(1,0,1)$ and $(1,1,0)$. Hence, intuitively, points in the vicinity of these points can be considered hard.


My own attempts: Note that the case $n = 2$ can be elegantly proven. For any $0 \leq x_1, x_2 \leq 1$ we have $-1 \leq 1 - 2x_1 \leq 1$ and $-1 \leq 1 - 2x_2 \leq 1$ and hence: \begin{align*} (1 - 2x_1)(1 - 2x_2) &\geq -1 & \Leftrightarrow \\ 1 - 2(x_1 + x_2) + 4x_1x_2 &\geq -1 & \Leftrightarrow \\ -2(x_1 + x_2) &\geq -2 - 4x_1x_2 & \Leftrightarrow \\ x_1 + x_2 &\leq 1 + 2x_1x_2 \end{align*} However, I do not see a way to generalize this proof.

$\endgroup$
3
$\begingroup$

Notice $$1 = \prod_{k=1}^n(x_k + (1-x_k)) = \sum_{A \subset [n]} \prod_{j\in A} x_j \prod_{k\in [n]\setminus A} (1-x_k) $$ and all the terms in RHS are non-negative. When one sum $A$ over a smaller collections of subsets of $[n]$, RHS will get smaller. Summing $A$ over $\mathcal{S}$, we obtain $$1 \ge \sum_{A \in \mathcal{S}} \prod_{j\in A} x_j\prod_{k \in [n]\setminus A}(1-x_k)$$ Notice for $A \in \mathcal{S}$, $[n]\setminus A$ are singletons, we can rewrite above as $$\begin{align} & 1 \ge \sum_{A \in\mathcal{S}}\left(\prod_{j\in A}x_j - \prod_{k\in[n]}x_k\right) = \left(\sum_{A\in \mathcal{S}} \prod_{j\in A} x_j\right) - |\mathcal{S}|\left(\prod_{k\in [n]}x_k\right)\\ \implies & \sum_{A\in \mathcal{S}} \prod_{j\in A} x_j\le 1 + |\mathcal{S}| \prod_{k\in [n]}x_k = 1 + n \prod_{k \in [n]}x_k \end{align} $$

$\endgroup$
  • $\begingroup$ Sweet! Thanks a lot. :) $\endgroup$ – arriopolis Mar 26 '18 at 19:17

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.