We have the set $\{X_1,X_2,X_3,\dotsc,X_n\}$. Given that $X_1+X_2+X_3+\dotsb +X_n = n$, prove that: $$\frac{X_1}{X_2} + \frac{X_2}{X_3} + \dotsb + \frac{X_{n-1}}{X_n} + \frac{X_n}{X_1} \leq \frac{4}{X_1X_2X_3\dotsm X_n} + n - 4$$

EDIT: yes, ${X_k>0}$ , forgot to mention :)

-
A proof for the $n=4$ case. – Mike Spivey Dec 24 '12 at 22:35

Let $$\begin{eqnarray} L(x_1,\ldots, x_n) &=& \frac{x_1}{x_2} + \frac{x_2}{x_3} + \ldots + \frac{x_n}{x_1} \\ R(x_1,\ldots, x_n) &=& \frac{4}{x_1 x_2 \ldots x_n} + n - 4 \\ f(x_1,\ldots, x_n) &=& R(x_1,\ldots, x_n) - L(x_1,\ldots, x_n) \end{eqnarray}$$

The goal is to prove that $f(x_1,\ldots, x_n) \ge 0$ for all $n$, given $x_i > 0$ and $\Sigma_i x_i = n$.

Proof [by complete induction]

The base case $n = 1$ is trivial. Now we prove the inequality for $n \ge 2$ assuming it holds for all values below $n$.

The sequence $s = x_1,\ldots, x_n$ is split in two subsequences : $s_\alpha = x_u,\ldots, x_{v-1}$ and $s_\beta = x_v, x_{v+1}, \ldots x_1 \ldots x_{u-1}$, where $1 \le u < v \le n$. Let $k = v-u$ such that the lengths of the sequences are $k$ and $n-k$. We write $\pi_\alpha, \pi_\beta$ for the products of the sequences, respectively, and $\sigma_\alpha, \sigma_\beta$ for their sums. With appropriate rescaling we get $f(\frac{k}{\sigma_\alpha} s_\alpha) \ge 0$ and $f(\frac{n-k}{\sigma_\beta} s_\beta) \ge 0$, by induction hypothesis, as $1 \le k \le n-1$.

It suffices now to show that $f(s) - f(\frac{k}{\sigma_\alpha} s_\alpha) - f(\frac{n-k}{\sigma_\beta} s_\beta) \ge 0$. Therefore we prove $R(s) - R(\frac{k}{\sigma_\alpha} s_\alpha) - R(\frac{n-k}{\sigma_\beta} s_\beta) \ge 0$ and $L(\frac{k}{\sigma_\alpha} s_\alpha) + L(\frac{n-k}{\sigma_\beta} s_\beta) - L(s)\ge 0$, in turn. $$\begin{eqnarray} R(s) - R(\frac{k}{\sigma_\alpha} s_\alpha) &-& R(\frac{n-k}{\sigma_\beta} s_\beta) \\ &=& \frac{4}{\pi_\alpha \pi_\beta} + n - 4 - \left(\frac{4 \sigma_\alpha^k}{k^k \pi_\alpha} +k -4 \right) - \left(\frac{4 \sigma_\beta^{n-k}}{(n-k)^{n-k} \pi_\beta} + n -k -4 \right) \\ & =& \frac{4}{\pi_\alpha \pi_\beta} \left( 1 + \pi_\alpha \pi_\beta - \frac{ \sigma_\alpha^k}{k^k} \pi_\beta - \frac{\sigma_\beta^{n-k}}{(n-k)^{n-k}} \pi_\alpha \right) \\ & =& \frac{4}{\pi_\alpha \pi_\beta} \left( \left( \frac{ \sigma_\alpha^k}{k^k} - \pi_\alpha \right) \left(\frac{\sigma_\beta^{n-k}}{(n-k)^{n-k}} - \pi_\beta \right) + 1 - \frac{\sigma_\beta^{n-k}}{(n-k)^{n-k}} \frac{ \sigma_\alpha^k}{k^k} \right) \end{eqnarray}$$

Both factors in the first product are positive: using Jensen's inequality we get $\log(\frac{ \sigma_\alpha^k}{k^k}) = k \log (\frac{\sigma_\alpha}{k}) \ge \Sigma_{i=u}^{v-1} \log(x_i) = \log(\pi_\alpha)$, and similar for the second factor. Furthermore we have $\log(\frac{\sigma_\beta^{n-k}}{(n-k)^{n-k}} \frac{ \sigma_\alpha^k}{k^k}) = n \left( \frac{n-k}{n} \log(\frac{\sigma_\beta}{n-k}) + \frac{k}{n} \log(\frac{ \sigma_\alpha}{k}) \right) \le n \log(\frac{\sigma_\beta}{n} + \frac{\sigma_\alpha}{n}) = 0$ again using Jensen's inequality. So the remaining terms are also positive.

Concerning the L-part we have: $$\begin{eqnarray} L(\frac{k}{\sigma_\alpha} s_\alpha) &+& L(\frac{n-k}{\sigma_\beta} s_\beta) - L(s) \\ &=& (\ldots + \frac{x_{v-1}}{x_u}) + (\ldots +\frac{x_{u-1}}{x_v}) - (\ldots + \frac{x_{v-1}}{x_v} + \ldots + \frac{x_{u-1}}{x_u} + \ldots) \\ &=& (x_{v-1} - x_{u-1}) (\frac{1}{x_u} - \frac{1}{x_v}) \end{eqnarray}$$ This if positive if $x_{v-1} \ge x_{u-1} \wedge x_{v} \ge x_{u}$, or $x_{v-1} \le x_{u-1} \wedge x_{v} \le x_{u}$. As we did not pose any constraints on $u$ and $v$ yet, it now remains to show that for any sequence one can always find $1 \le u < v \le n$ for which this is fulfilled. First, if $x_{i-1} \le x_i \le x_{i+1}$ for some $i$, or $x_{i-1} \ge x_i \ge x_{i+1}$ (for $n$ odd this is always the case), then we can simply choose $u=i-1, v=i$. So now assume we have a "crown" of successive up and down transitions while looping through the sequence. If for some $i, j$ with $x_i \le x_{i+1}$ and $x_j \le x_{j+1}$, none of the intervals $[x_i \le x_{i+1}]$ and $[x_j \le x_{j+1}]$ contains the other completely, then appropriate $u$ and $v$ can be defined. So now assume that all "up-intervals" $[x_i, x_{i+1}]$ with $x_i \le x_{i+1}$ are strictly ordered (by containment). Looping through these up-intervals we must encounter a local maximum such that $[x_{i-2}, x_{i-1}] \subseteq [x_{i}, x_{i+1}] \supseteq [x_{i+2}, x_{i+3}]$. Hence $x_{i-1} \le x_{i+1}$ and $x_{i} \le x_{i+2}$, so with $u=i, v=i+2$ also this last case is covered.

-
exactly the way I did it! Well done :) – Or Cyngiser Feb 17 '13 at 16:32