2

Let $x_1,x_2,...,x_n$ be real numbers in $[0;1]$. Prove that

$$\sum_{1\le i<j \le n}x_ix_j \le 2+\sum_{1\le i<j<k \le n}x_ix_jx_k$$

I thinks it can be solved by induction and function, like this inequality $$\sum x_i \le 1+\sum_{1\le i<j \le n}x_ix_j$$

Thanks

clark
  • 15,327
tangkhaihanh
  • 917

1 Answers1

2

Induction is indeed a good idea.

If you start from the following fact :

Fact 1 . Let $f$ be an affine univariate function on $[0,1]$, $f(x_1)=ax_1+b$. Then $f$ is nonnegative on $[0,1]$ iff $f$ is nonnegative on the boundary, i.e. iff $f(0)$ and $f(1)$ are both nonnegative.

Iterating this, one obtains

Fact 2 . Let $f$ be a “locally affine” $n$-variate function on $[0,1]^n$, $f(x_1,x_2,\ldots ,x_n)=\sum_{I \subseteq \lbrace 1,2, \ldots ,n\rbrace } a_Ix_I$ (where the $a_I$ are constants and $x_I=\prod_{i\in I}x_i$ ). Then $f$ is nonnegative on $[0,1]^n$ iff $f$ is nonnegative on the boundary, i.e. iff $f(x_1,x_2,\ldots ,x_n)$ is nonnegative when all the $x_i$ are equal to $0$ or $1$.

So it will suffice to show the inequality when all the $x_i$ are equal to $0$ or $1$. If $s$ of those numbers are equal to one, the others are zero, so $$ \sum_{1\le i<j \le n}x_ix_j=\binom{s}{2}, \ \sum_{1\le i<j<k \le n}x_ix_jx_k=\binom{s}{3} $$

So all we need to show now is $\binom{s}{2} \leq 2+\binom{s}{3}$ ; but

$$ 2+\binom{s}{3}-\binom{s}{2}=(s+1)(s-3)(s-4) $$

which concludes the proof.

Ewan Delanoy
  • 61,600