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$

1 Answer 1

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$
1
  • $\begingroup$ Sweet! Thanks a lot. :) $\endgroup$
    – arriopolis
    Commented Mar 26, 2018 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .