Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question
    
@DanBrumleve $X_1 + X_2 + X_3 \neq 3$ in your counterexample. –  user17762 Dec 24 '12 at 20:55
1  
Counterexample: { 0.001, -1.001, 4 }. Surely $X_k > 0$ was the intent? –  Erick Wong Dec 24 '12 at 20:58
1  
@OP You might want $X_k > 0$, else for $n=2$, we have $$\dfrac{X_1}{X_2} + \dfrac{X_2}{X_1} \leq \dfrac4{X_1 X_2} + 2 \implies X_1^2 + X_2^2 \leq 4 + 2X_1 X_2 \implies (X_1 - X_2)^2 \leq 4$$ Since $X_2 = 2-X_1$, this gives us $(X_1-1)^2 \leq 1$. Choose $X_1 < 0 $. To get a contradiction. –  user17762 Dec 24 '12 at 21:02
1  
A proof for the $n=4$ case. –  Mike Spivey Dec 24 '12 at 22:35

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
exactly the way I did it! Well done :) –  Or Cyngiser Feb 17 '13 at 16:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.