Show that $\sum_{1\le iLet $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
 A: 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.
