Prove $ \frac{x_1-x_2}{x_n+x_1} + \frac{x_2-x_3}{x_1+x_2}+\cdots+ \frac{x_n-x_1}{x_{n-1} +x_n}\le 0$ s.t. $x_1+\cdots+x_n=1$

Question

Is it true that: $$ f_n(x_1,\ldots,x_n)=\frac{x_1-x_2}{x_n+x_1} + \frac{x_2-x_3}{x_1+x_2}+\cdots+ \frac{x_n-x_1}{x_{n-1} +x_n}\le 0 $$ for $x_1,\ldots,x_n>0$, such that $x_1+\cdots+x_n=1$?

It is a cyclic inequality that I came up with while proving similar ones, although it may well be already solved/proposed somewhere else. Equality is attained at $x_1=\cdots=x_n=1/n$.

The first approach I’ve tried is to represent the inequality equivalently as $$ n\le \frac{x_1 +x_3}{x_1+x_2} + \frac{x_2+x_4}{x_2+x_3}+\cdots+\frac{x_n+x_2}{x_n+x_1}, $$ which is trivially true for $n=3$ by AM-GM, but not so for $n>3$, since the terms don’t cancel.

I’ve also tried the following approach: let $x_1$ be the largest wlog, then we can examine the function $$ g(t)=f_n(x_1-t, x_2 +t,\ldots,x_n) = \frac{x_1-x_2-2t}{x_n+x_1-t} + \frac{x_2+t-x_3}{x_1+x_2}+ \frac{x_3-x_4}{x_2+t+x_3} +\cdots+ \frac{x_n-x_1+t}{x_{n-1} +x_n} $$ and see if it is increasing for small enough $t$. Then we can proceed by generating sequences that approach the average while increasing the value of $f$. For example $$ g(t)-g(0)=\frac{t}{x_1+x_2}+\frac{t}{x_n+x_{n-1}}-t\frac{x_1+x_2+2x_n}{(x_1+x_n-t)(x_1+x_n)}-t\frac{x_3-x_4}{(x_2+x_3+t)(x_2+x_3)}, $$ but not sure if this is nonnegative.

EDIT: I've made some progress towards the $n=5$ case.

Let us assume wlog that $x_1$ is the largest throughout the proof. We also know that the $n=4$ case is true (see comments). Thus $$ f_5(x_1,\ldots,x_5)=f_4(x_2,\ldots,x_5)+\frac{x_2-x_1}{x_4+x_5}+\frac{x_1-x_2}{x_5+x_1}+\frac{x_2-x_3}{x_1+x_2}-\frac{x_2-x_3}{x_5+x_1}\leq\\\leq \frac{x_2-x_1}{x_4+x_5}+\frac{x_1-x_2}{x_5+x_1}+\frac{x_2-x_3}{x_1+x_2}-\frac{x_2-x_3}{x_5+x_1}=\\=\frac{(x_1-x_2)(x_4-x_1)}{(x_1+x_5)(x_4+x_5)}+\frac{(x_2-x_3)(x_5-x_1)}{(x_1+x_2)(x_2+x_5)}.\tag{1}\label{ineq:1} $$ By successively cyclically permuting the sequence we also derive the inequalities: \begin{align} f_5(x_1,\ldots,x_5) &\leq \frac{(x_2-x_3)(x_5-x_2)}{(x_2+x_1)(x_5+x_1)}+\frac{(x_3-x_4)(x_1-x_2)}{(x_2+x_3)(x_3+x_1)}\label{ineq:2}\tag{2}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_3-x_4)(x_1-x_3)}{(x_3+x_2)(x_1+x_2)}+\frac{(x_4-x_5)(x_2-x_3)}{(x_3+x_4)(x_4+x_2)}\label{ineq:3}\tag{3}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_4-x_5)(x_2-x_4)}{(x_4+x_3)(x_2+x_3)}+\frac{(x_5-x_1)(x_3-x_4)}{(x_4+x_5)(x_5+x_3)}\label{ineq:4}\tag{4}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_5-x_1)(x_3-x_5)}{(x_5+x_4)(x_3+x_4)}+\frac{(x_1-x_2)(x_4-x_5)}{(x_5+x_1)(x_1+x_4)}\label{ineq:5}\tag{5}. \end{align}

Now we consider several cases.

Case 1: If $x_2\geq x_3$ then $\eqref{ineq:1}$ is $\leq 0$.

Case 3: If $x_2 < x_3 \leq x_4 \leq x_5$ then $\eqref{ineq:2}$ is $\leq 0$.

Case 2: If $x_2 < x_3 \leq x_4$ and $x_4 > x_5$ then $\eqref{ineq:3}$ is $\leq 0$.

Case 4: If $x_2 < x_3$, $x_3 > x_4, x_4 \leq x_5$ and $x_3 \geq x_5$ then $\eqref{ineq:5}$ is $\leq 0$.

Case 5: If $x_2 < x_3$, $x_3 > x_4, x_4 \leq x_5$ and $x_2 \geq x_4$ then $\eqref{ineq:4}$ is $\leq 0$.

Case 6: If $x_2 < x_3$, $x_3 > x_4, x_4 > x_5$ and $x_2 \leq x_4$ then $\eqref{ineq:4}$ is $\leq 0$.

There are two more cases to consider.

Case 7: If $x_3>x_2>x_4 > x_5$ then it seems to be the case that $$ f_5(x_1,\ldots,x_5) \leq f_5(x_1,x_2,x_4,x_3,x_5). $$ via simulation. If proven true, then we just need to apply case 1 to it and we're done.

Case 8: Since case 4 and 5 are true independently, we need consider only $x_5>x_3>x_4>x_2$ as a subcase. However I haven't the slightest clue how to approach this.

EDIT 2 According to WolframAlpha, it seems that the individual fractions are concave functions of $\mathbf{x}=(x_1,\ldots,x_n)$. Does that mean that $f$ is also concave, therefore we can bound by $$ f_n(\mathbf{x}) \leq f_n(\mathbf{1}/n) + \nabla f_n(\mathbf{1}/n)^T(\mathbf{x} - \mathbf{1}/n) = 0? $$

Answer 1

The inequality is false for $n = 6$ (and any even $n > 6$ also). I drop the requirement that the sum be equal to $1$, since one can always scale any counter-example if desired.

As an example, one has $$ f(0.01,~1,~0.05,~1,~0.10,~1.10) \approx 0.00033 > 0. $$ This is inspired by counter-examples to Shapiro's inequality, which look for $x$ under the form $$ x(\varepsilon) := (\varepsilon a_1 ,~1 + \varepsilon a_2,~\varepsilon a_3 ,~1 + \varepsilon a_4,~\varepsilon a_5,~1 + \varepsilon a_6), $$ for well-chosen coefficients $a_i$ and $\varepsilon$ small enough. I use $a = (1, 0, 5, 0, 10, 10)$ for which $$ f(x(\varepsilon)) = 19 \varepsilon^2 + O(\varepsilon^3) $$ by Taylor expansion, which is indeed positive (with $x_i > 0$) for $\varepsilon > 0$ small enough.

---

Edit: For any even $n \geq 6$, one can use $x = (0.10,~1.10,~0,~1.05,~0,~1,\dotsc,~0,~1)$ which is of the form $x(\varepsilon) = (2\varepsilon,~1+2\varepsilon,~0,~1+\varepsilon,~0,~1, ~\dotsc,~0,~1)$, where $\varepsilon = 0.05$. The last $(0,1)$ are repeated as much as necessary. Taylor expansion proves that $f(x(\varepsilon)) = \varepsilon^2 + O(\varepsilon^3)$. If desired, the zero components can be replaced by $\varepsilon^3$ to ensure $x_i > 0$.

Answer 2

Remarks: The inequality is not true for even $n\ge 6$, or odd $n\ge 13$. The inequality is true for $n = 3, 4, 5$. The remaining cases are $n = 7, 9, 11$.

Some results for even $n\ge 6$ or odd $n\ge 13$ etc.

Since the inequality is homogeneous, we drop the condition $x_1 + x_2 + \cdots + x_n = 1$ for convenience. In other words, we consider the following problem.

Problem. Let $n\ge 3$. Let $x_1, x_2, \cdots, x_n \ge 0$ with $(x_1+x_2)(x_2 + x_3)\cdots (x_n + x_1) \ne 0$. Prove or disprove $$\sum_{\mathrm{cyc}} \frac{x_2 - x_3}{x_1 + x_2} \le 0. \tag{1}$$

Denote LHS by $f_n(x_1, x_2, \cdots, x_n)$. We have the relation: $$f_{n+2}(x_1, x_2, \cdots, x_n, x_1, x_n) = f_n(x_1, x_2, \cdots, x_n). \tag{2}$$ Note: This is actually Wenlan Yan (a Chinese Scholar)'s idea for a related problem (see my another answer). The proof is easy. Indeed, we have \begin{align*} &f_{n+2}(x_1, x_2, \cdots, x_n, x_1, x_n)\\ ={}& \frac{x_2 - x_3}{x_1 + x_2} + \cdots + \frac{x_n - x_1}{x_{n-1} + x_n} + \frac{x_1 - x_n}{x_n + x_1} + \frac{x_n - x_1}{x_1 + x_n} + \frac{x_1 - x_2}{x_n + x_1}\\ ={}& \frac{x_2 - x_3}{x_1 + x_2} + \cdots + \frac{x_n - x_1}{x_{n-1} + x_n} + \frac{x_1 - x_2}{x_n + x_1}\\ ={}& f_n(x_1, x_2, \cdots, x_n). \end{align*}

From (2), we know that if (1) is true for $n + 2$, then (1) is also true for $n$. In other words, if (1) is not true for $n$, then (1) is not true for $n + 2$. Using this fact, we obtain some results as follows.

1. The inequality is not true for even $n\ge 6$.

We have $$f_6(40,3,40,5,45,0) ) = \frac{11}{15480} > 0.$$ Thus, (1) is not true for $n = 6$.

So, (1) is not true for even $n\ge 6$.

2. The inequality is not true for odd $n\ge 13$.

We have $$f_{13}(4,4,6,4,8,0,6,0,4,1,4,2,4) = \frac{1}{60} > 0.$$ Thus, (1) is not true for $n = 13$.

Thus, (1) is not true for odd $n\ge 13$.

Answer 3

Remarks: Here is a proof for $n = 5$ case. The identity is verified by Maple. The Maple expression of $f(a,b,c,d,e)$ is given at the end if someone wants to verify it by CAS (Computer Algebra Systems).

Problem. Let $a, b, c, d, e \ge 0$ with $(a+b)(b+c)(c+d)(d+e)(e+a) \ne 0$. Prove that $$\frac{a - b}{e + a} + \frac{b - c}{a + b} + \frac{c - d}{b + c} + \frac{d - e}{c + d} + \frac{e - a}{d + e} \le 0.$$

Proof.

We have \begin{align*} &-\frac{a - b}{e + a} - \frac{b - c}{a + b} - \frac{c - d}{b + c} - \frac{d - e}{c + d} - \frac{e - a}{d + e}\\[6pt] ={}& \frac{f(a,b,c,d,e) + f(b,c,d,e,a) + f(c,d,e,a,b) + f(d,e,a,b,c) + f(e,a,b,c,d)}{(a+b)(b+c)(c+d)(d+e)(e+a)} \end{align*} where \begin{align*} f(a, b, c, d, e) &:= {\frac {1}{540}}\,cab \left( 23\,a-15\,d-8\,e \right) ^{2}+{\frac {11} {540}}\,cab \left( a-d \right) ^{2}\\[6pt] &\qquad + {\frac {1}{945}}\,abd \left( 30\,a-30\,d+7\,c-7\,e \right) ^{2} + {\frac {2213}{108000}}\,{a}^{2}c \left( b-e \right) ^{2}\\[6pt] &\qquad +{ \frac {1}{2025}}\,c \left( 36\,ab+4\,ad-31\,ae+6\,bd-30\,be+15\,ce \right) ^{2}\\[6pt] &\qquad +{\frac {1}{16200}}\,c \left( 31\,ab+24\,ad+59\,ae-114\,b d+120\,be-120\,ce \right) ^{2}\\[6pt] &\qquad +{\frac {1}{16200}}\,c \left( 3\,ab+4\,a d-13\,ae+6\,bd \right) ^{2} +\frac{1}{21}\,abd \left( a-d \right) ^{2}\\[6pt] &\qquad +{\frac {1}{324000}}\,c \left( 301\,ab+240 \,ad-301\,ae-240\,bd \right) ^{2}. \end{align*}

We are done.

---

Maple expression of $f(a,b,c,d,e)$:

(1/540)*c*a*b*(23*a-15*d-8*e)^2+(11/540)*c*a*b*(a-d)^2+(1/21)*a*b*d*(a-d)^2+(1/945)*a*b*d*(30*a-30*d+7*c-7*e)^2+(1/2025)*c*(36*a*b+4*a*d-31*a*e+6*b*d-30*b*e+15*c*e)^2+(1/16200)*c*(31*a*b+24*a*d+59*a*e-114*b*d+120*b*e-120*c*e)^2+(1/16200)*c*(3*a*b+4*a*d-13*a*e+6*b*d)^2+(1/324000)*c*(301*a*b+240*a*d-301*a*e-240*b*d)^2+(2213/108000)*a^2*c*(b-e)^2

Answer 4

Related inequalities:

Remarks: Here I introduce the No. 13 of Xuezhi Yang's 22 conjectures. I think we can find some similar results, and the strategy for it is helpful. More details are given in https://artofproblemsolving.com/community/c6h2718098

---

At the Symposium in Elementary Mathematics (in 2009, China), Mr. Xuezhi Yang proposed 22 conjectures in inequalities. No. 13 is the following:

Conjecture 13 (Xuezhi Yang): Let $x_1, x_2, \cdots, x_n \ge 0$. For $n = 5, 6, \cdots, 13$ and $ n = 15, 17, 19, 21, 23$, prove or (disprove) $$\sum_{\mathrm{cyc}} \frac{x_1 - x_2}{x_2 + x_3}\ge 0.$$

According to Mr. Xuezhi Yang's book (written in Chinese, 2009), the case $n = 3, 4$ was proposed in 1990.

According to the results of some Chinese scholars, the inequality is not true for $n = 6, 8, 10, 12$ and $n = 13, 15, 17, 19, 21, 23$; and the inequality is true for $n = 5$. The remaining cases are $n = 7, 9, 11$.

For general $n$: According to the results of Wenlan Yan (a Chinese scholar), $f_{n + 2} \ge 0$ implies $f_n \ge 0$ where $f_n$ denotes the LHS of the inequality. Thus, the inequality is not true for $n\ge 6$ and even, or $n\ge 13$ and odd.

Answer 5

This is too long for a comment and since it was requested, here is a Python script to search for counterexamples using a genetic algorithm. It uses first library I found for genetic algorithms with basic settings, in this case PyGAD. I am sure things like crossover & mutation can be tuned as well as the code optimized, but it already finds (counter)examples quickly enough. Also it searches without the $x_1+\dots +x_n=1$ restriction, so scale the solutions if needed.

Note: In current implementation the genes (individual $x_i$s) can be negative so I am working with absolute values.

import pygad
def check(n):
def fitness_func(ga_instance, solution, solution_idx):
    X = [abs(x) for x in solution]
    S = 0
    for i in range(n):
        if X[(i - 1)] + X[i] == 0:
            return -1
        S += (X[i] - X[(i + 1) % n]) / (X[(i - 1) % n] + X[i])

    return S

fitness_function = fitness_func

num_generations = 100
num_parents_mating = 4

sol_per_pop = 50
num_genes = n

init_range_low = 0
init_range_high = 1

parent_selection_type = "sss"
keep_parents = 1

crossover_type = "single_point"

mutation_type = "random"
mutation_percent_genes = "default"
mutation_num_genes = 1

for attempt in range(200):
    gene_type = [float] * n

    ga_instance = pygad.GA(num_generations=num_generations,
                           num_parents_mating=num_parents_mating,
                           fitness_func=fitness_function,
                           sol_per_pop=sol_per_pop,
                           num_genes=num_genes,
                           init_range_low=init_range_low,
                           init_range_high=init_range_high,
                           parent_selection_type=parent_selection_type,
                           keep_parents=keep_parents,
                           crossover_type=crossover_type,
                           mutation_type=mutation_type,
                           mutation_percent_genes=mutation_percent_genes,
                           mutation_num_genes=mutation_num_genes,
                           gene_type=gene_type)

    ga_instance.run()

    solution, solution_fitness, solution_idx = ga_instance.best_solution()

    if solution_fitness > 0:
        return [abs(x) for x in solution], solution_fitness

return None, None



for n in range(3, 20):
    sol, fitness = check(n)
    if sol is None:
        print(f"{n}: counterexample not found")
    else:
        print(f"{n}: counterexample found: {sol}, {fitness}")

Here is an example output when searching in range $n=3,4,\dots,19$:

3: counterexample not found
4: counterexample not found
5: counterexample not found
6: counterexample found: [0.1127451443655707, 0.984047056559817, 0.0006891812689751031, 0.8747821381098065, 0.07973695836666417, 0.8923772229596213], 0.0008424173573100546
7: counterexample not found
8: counterexample found: [0.7555196233906635, 0.002284834826341453, 0.6066683059689687, 0.035242433747941115, 0.5500023844379328, 0.13912705899813071, 0.6227234634922209, 0.17019419483944864], 0.008692855805153221
9: counterexample not found
10: counterexample found: [0.2865983261600199, 1.0494435537886102, 7.556348092685461e-06, 0.8026083255492057, 0.002541750372603957, 0.6226469717045814, 0.14437176959682485, 0.6626180639943181, 0.28551562949546505, 0.8593656766544738], 0.0333552418370901
11: counterexample not found
12: counterexample found: [0.4598963440624112, 1.0406403276703875, 0.3690044176216819, 1.2251453839093667, 0.00272450987067574, 0.882985035974145, 0.0007653966593861306, 0.6372299973803794, 0.1551872312511604, 0.6231971103898529, 0.33989248661093063, 0.7628276059879917], 0.05556447423696165
13: counterexample found: [0.5038459363748282, 1.3133558069280669, 0.008177075932440991, 0.8967924375504703, 0.022380104007717172, 0.6467699203174091, 0.1584673377078757, 0.5933052961735467, 0.38879601764418403, 0.6066572584225334, 0.6466163377832892, 0.642257389205082, 1.003618621480073], 0.02230627298168064
14: counterexample found: [0.2936805194030777, 1.101167116014886, 0.003222280282728973, 0.7995927516297595, 0.007168899301610132, 0.6585845937517883, 0.11700998100189608, 0.6323059856367423, 0.24031085433340538, 0.6772291101836613, 0.36253497690141756, 0.8111908100214541, 0.3547934092222419, 0.9573210731042766], 0.06106131972134221
15: counterexample found: [0.5477099288485329, 0.14730657809570247, 0.5376848427524631, 0.380555167689996, 0.637009671846778, 0.6422098324140793, 0.7022963361696113, 1.0057284457810964, 0.6616176612213105, 1.561049295175914, 0.005156204220376437, 1.0907727535676819, 0.004646387587251555, 0.7780822896796564, 0.0028204349956135744], 0.08453066977596169
16: counterexample found: [0.6397938698339589, 0.28234049273033257, 0.6904935018333977, 0.3804797750754091, 0.7725996710450245, 0.4933655531224208, 0.9628793435340853, 0.5205017242374805, 1.2076892091095182, 0.3036581190825709, 1.2630253424373237, 0.003934738509556834, 0.883203765847461, 0.005181489305189579, 0.6380104290746482, 0.1365655586542045], 0.08747753124842539
17: counterexample found: [0.8089562532936915, 0.7671223686995414, 1.3097405784811802, 0.6274276398114672, 1.6859621526863962, 0.0008962964378883553, 1.1708809051169948, 0.005156967931749024, 0.842201107879035, 0.00443971922676234, 0.5871581225772036, 0.08072680836604595, 0.475399915499073, 0.24305503363159742, 0.5164480153919089, 0.49097915717416885, 0.6500685676958009], 0.12352471651055946
18: counterexample found: [0.4941360812428496, 0.9855792458054153, 0.39214096423944556, 1.2175256082754318, 0.013009837737754881, 0.9115555653063624, 0.0038629864364830846, 0.6531094666853975, 0.007590820745124405, 0.4599560432187483, 0.06023746725062318, 0.4142086539545594, 0.18738989383376248, 0.41555600252250013, 0.2969341489356452, 0.4925680529149822, 0.4268911172788926, 0.6498808193467815], 0.14161415469210945
19: counterexample found: [0.43397023970898874, 0.2762568644315543, 0.48850362912513257, 0.4224351109668695, 0.5431450504814156, 0.6011817391126395, 0.5937733459216573, 0.853280211198245, 0.5916627588456863, 1.1142048188624363, 0.3181712042000304, 1.1479101992709562, 0.010300281098192143, 0.8080262936090858, 0.024535790039653227, 0.6318421262424485, 0.006276206316145894, 0.4577509718418442, 0.12785211607940616], 0.12041951610009682

This is consistent with findings in other answers, and for remaining unsolved cases $7,9,11$ it finds no counterexample (even if we try to search for much longer, I've had it running for couple hours and no luck). This of course proves nothing but at least gives some numeric evidence that the inequality might hold in these three cases.

I would also like to point out a similarity to Shapiro inequality which was already touched on in another answer. Shapiro has first even counterexample for $n=14$, while first odd for $n=25$, and our computations suggest that this inequality has also odd counterexample higher than the even one. So I believe that studying Shapiro's and related proofs might help with the cases $n=7,9,11$.

Answer 6

Using your notation for $f_n(x_1,\ldots,x_n)$, notice if we reverse the variables and change the sign, as well as the order of first $n-1$ terms, we get the equivalent

$$ -f_n(x_n,\ldots,x_1)=\sum_{cyc}\frac{x_i-x_{i+1}}{x_{i+1}+x_{i+2}}=\frac{x_1-x_2}{x_2 +x_3}+\frac{x_2-x_3}{x_3 +x_4}+\dots+\frac{x_n-x_1}{x_1 +x_2}\geq 0.\tag{*} $$

This happens to be the related inequality as posted by River Li in their answer (No. 13 of Xuezhi Yang's 22 conjecture) - so not only they are related but they are equivalent. Furthermore I have checked a literature and found this has been apparently proven for $n=3,4,5,7$, namely in Automated Inequality Proving and Discovering by Bican Xia and Lu Yang (2016) we find:

Page 290, Example 10.15 (Problem 7.14 of [Cirtoaje et al. (2009)]):

$$ \frac{a-b}{b+c}+\frac{b-c}{c+d}+\frac{c-d}{d+e}+\frac{d-e}{e+a}+\frac{e-a}{a+b}\geq 0 $$

Page 291, Example 10.19 (Vasc's Conjecture with 6 variables):

$$ \frac{a_1-a_2}{a_2 +a_3}+\frac{a_2-a_3}{a_3 +a_4}+\frac{a_3-a_4}{a_4 +a_5}+\frac{a_4-a_5}{a_5 +a_6}+\frac{a_5-a_6}{a_6 +a_1}+\frac{a_6-a_1}{a_1 +a_2}\geq 0 $$ where $a_i>0$, ($i=1,\dots,6$). It is easy to see that Example 10.15 is a special case of Vasc's Conjecture when the number of variables is $5$.

The inequality does not hold. An output counterexample is $$a_1=84,a_2=7,a_3=79,a_4=5,a_5=76,a_6=1.$$ Let $n$ be the number of variables in Vasc's Conjecture. By SDS method, we have proven that the inequality holds for $n=3,4,5,7$.

Page 291, Example 10.20 (Vasc's Conjecture with 7 variables):

$$ \frac{a_1-a_2}{a_2 +a_3}+\frac{a_2-a_3}{a_3 +a_4}+\frac{a_3-a_4}{a_4 +a_5}+\frac{a_4-a_5}{a_5 +a_6}+\frac{a_5-a_6}{a_6 +a_7}+\frac{a_6-a_7}{a_7 +a_1}+\frac{a_7-a_1}{a_1 +a_2}\geq 0 $$ where $a_i>0$ for $i=1,\dots,7$.

Chen (2008) made use of the Parallel Successive Difference Substitution to verify this inequality. It runs on 18 nodes of a set of HP Proliant DL360 Intel xeon 2.8Ghz, 2GB memory, Windows 2003 Server, with Maple 10, and proved that the inequality holds in CPU time 9128.92 seconds.

So we are given a counterexample to $n=6$ to our original problem, as well as we know the cases $n=3,4,5,7$ have been verified by the successive difference substitution (SDS) method described earlier in the book. Unfortunately, we are not given any analytical proof, the method relies on heavy computations (large number of polynomials are generated in the process). Still it might be worth reproducing the result and trying the algorithm on the last two cases $n=9,11$.

As for reproducing the result, I've implemented a version of the algorithm in Maple and verified the cases $n=3,4,5,7$. I will show how the method works for $n=5$ and then just summarize the case $n=7$.

Consider $n=5$. We want to have inequality with polynomial on one side, so we first multiply by (positive) $\prod_{cyc}(x_2+x_3)$. Then since the inequality is cyclic, we can WLOG assume $x_1$ is the maximal of the $x_i$ values. Now we consider $4!=24$ orderings of the remaining variables, for example for $x_1\geq x_2 \geq \dots \geq x_5$ we let \begin{alignat*}{5} x_1&=t_1+&t_2+&t_3+&t_4+&t_5\\ x_2&= &t_2+&t_3+&t_4+&t_5\\ x_3&= & &t_3+&t_4+&t_5\\ x_4&=& & &t_4+&t_5\\ x_5&=& & & &t_5. \end{alignat*} It can be verified that all $x_i>0$ if and only if all $t_i > 0$. Substituting to the original polynomial we get a polynomial in $t_1,t_2,t_3,t_4,t_5$ with only non-negative coefficients, and so it is positive for positive $t_i$'s. Checking the remaining $23$ orderings and applying corresponding substitutions (largest number, i.e. $x_1$ being $t_1+t_2+\dots+t_5$, second largest $t_2+\dots +t_5$ and so on), we find there are only three polynomials that have a negative coefficient. For example one of them being:

$$ t_1^3t_2^2 + 3t_1^3t_2t_3 + 3t_1^3t_2t_4 + 4t_1^3t_2t_5 + 2t_1^3t_3^2 + 4t_1^3t_3t_4 + 6t_1^3t_3t_5 + 2t_1^3t_4^2 + 6t_1^3t_4t_5 + 4t_1^3t_5^2 + 3t_1^2t_2^3 + 10t_1^2t_2^2t_3 + 8t_1^2t_2^2t_4 + 12t_1^2t_2^2t_5 + 9t_1^2t_2t_3^2 + 13t_1^2t_2t_3t_4 + 24t_1^2t_2t_3t_5 + 5t_1^2t_2t_4^2 + 20t_1^2t_2t_4t_5 + 16t_1^2t_2t_5^2 + 3t_1^2t_3^3 + 7t_1^2t_3^2t_4 + 12t_1^2t_3^2t_5 + 6t_1^2t_3t_4^2 + 20t_1^2t_3t_4t_5 + 16t_1^2t_3t_5^2 + 2t_1^2t_4^3 + 10t_1^2t_4^2t_5 + 16t_1^2t_4t_5^2 + 8t_1^2t_5^3 + 3t_1t_2^4 + 12t_1t_2^3t_3 + 9t_1t_2^3t_4 + 14t_1t_2^3t_5 + 15t_1t_2^2t_3^2 + 19t_1t_2^2t_3t_4 + 36t_1t_2^2t_3t_5 + 4t_1t_2^2t_4^2 + 22t_1t_2^2t_4t_5 + 20t_1t_2^2t_5^2 + 8t_1t_2t_3^3 + 12t_1t_2t_3^2t_4 + 26t_1t_2t_3^2t_5 \color{red}{-} t_1t_2t_3t_4^2 + 18t_1t_2t_3t_4t_5 + 24t_1t_2t_3t_5^2 \color{red}{-} 4t_1t_2t_4^3 \color{red}{-} 4t_1t_2t_4^2t_5 + 8t_1t_2t_4t_5^2 + 8t_1t_2t_5^3 + 2t_1t_3^4 + 5t_1t_3^3t_4 + 8t_1t_3^3t_5 + 3t_1t_3^2t_4^2 + 10t_1t_3^2t_4t_5 + 8t_1t_3^2t_5^2 + t_2^5 + 5t_2^4t_3 + 4t_2^4t_4 + 6t_2^4t_5 + 9t_2^3t_3^2 + 14t_2^3t_3t_4 + 22t_2^3t_3t_5 + 5t_2^3t_4^2 + 16t_2^3t_4t_5 + 12t_2^3t_5^2 + 8t_2^2t_3^3 + 19t_2^2t_3^2t_4 + 28t_2^2t_3^2t_5 + 14t_2^2t_3t_4^2 + 38t_2^2t_3t_4t_5 + 28t_2^2t_3t_5^2 + 4t_2^2t_4^3 + 12t_2^2t_4^2t_5 + 16t_2^2t_4t_5^2 + 8t_2^2t_5^3 + 4t_2t_3^4 + 15t_2t_3^3t_4 + 18t_2t_3^3t_5 + 22t_2t_3^2t_4^2 + 42t_2t_3^2t_4t_5 + 24t_2t_3^2t_5^2 + 17t_2t_3t_4^3 + 34t_2t_3t_4^2t_5 + 24t_2t_3t_4t_5^2 + 8t_2t_3t_5^3 + 6t_2t_4^4 + 14t_2t_4^3t_5 + 8t_2t_4^2t_5^2 + t_3^5 + 6t_3^4t_4 + 6t_3^4t_5 + 15t_3^3t_4^2 + 26t_3^3t_4t_5 + 12t_3^3t_5^2 + 20t_3^2t_4^3 + 46t_3^2t_4^2t_5 + 32t_3^2t_4t_5^2 + 8t_3^2t_5^3 + 14t_3t_4^4 + 42t_3t_4^3t_5 + 36t_3t_4^2t_5^2 + 8t_3t_4t_5^3 + 4t_4^5 + 16t_4^4t_5 + 20t_4^3t_5^2 + 8t_4^2t_5^3. $$

For these three polynomials the process above is repeated (the successive part of the algorithm) for all orderings, this is because the new polynomials are no longer cyclic and we have to consider all permutations. Next iteration results only in non-negative coefficients, hence proving the case $n=5$.

For $n=7$, similarly as above we first check $6!=720$ orderings to find $72$ polynomials with a negative coefficient. Repeating the process on these the next iteration yields only polynomials with non-negative coefficients, proving the case $n=7$.

I've briefly tried $n=9$ but each iteration took too long and generated too many new polynomials to check in next iteration, so it does not seem to be efficient in the current form (not to mention $n=11$).

Answer 7

Just some remark :

We have the following theorem :

Define :

$$f\left(x\right)=\frac{x+b}{x+c},g\left(x\right)=f\left(1-x\right)+f\left(x\right)-f\left(1-x\right)f\left(x\right)$$

Let $b,c\in(0,1),x\in(0,1)$ such that then we have :

$$g''(x)\leq 0,g(x)-g(0)\geq 0$$

Now if :

$$h\left(x\right)=f\left(1-x\right)f\left(x\right)$$

Then for $b\leq c$ we have :

$$h(x)\geq h(0),f(1-x)$$

And if $c\leq b$ we have :

$$h\left(x\right)-h\left(\frac{1}{2}\right)\geq 0$$

On the other hand we can squeeze $f(1-x)$ as we have for $c\in(0,1),b\in[0,0.2],x\in[0,1/2]$ then :

$$t\left(x\right)=\frac{\left(1-x^{2}+b\right)}{1-x^{2}+c}-\frac{5}{3}\left(x^{2}+b+c\right),\frac{\left(t\left(0\right)-t\left(\frac{1}{\sqrt{2}}\right)\right)}{0-\frac{1}{\sqrt{2}}}\sqrt{x}+t\left(0\right)\leq t\left(\sqrt{x}\right)$$

---

---

---

---

A totally different way using integral :

Consider the integral :

$$f\left(x\right)=\frac{x+b}{x+c},\int_{0}^{x}f\left(t\right)dt=h(x)-h(0),h(x)=\left(b-c\right)\ln\left(c+x\right)+x$$

Then plugging $x_i-x_{i+1}=a_ia_j$ so the sum is zero we can use A conditional negative definite quadratic form involving $\ln$ function

We start in setting $x=1$ so we have :

$$\int_{0}^{1}f\left(t\right)dt=\left(b-c\right)\ln\left(c+1\right)+1-\left(b-c\right)\ln\left(c\right)$$

using the link above in the case $n=9$ we have that the sum of difference of log is positive so we have :

$$\sum_{cyc}^{}\int_{0}^{1}f\left(t\right)dt\geq n$$

then integrating with the tangent lemma and if the sum to show is convex and the function to integrate is finite for all $x\in(\varepsilon,1]$ then we can conclude as OP did.

We have someting like :

$$g\left(x\right)=\frac{x+b}{x+c}+\frac{\left(x+a\right)}{x+d}+...+\frac{x+u}{x+v}$$

Then for $t,x\in[0,1]$ :

$$\int_{0}^{t}\left(\frac{x+b}{x+c}+\frac{\left(x+a\right)}{x+d}+...+\frac{x+u}{x+v}\right)dx-g\left(x\right)\left(t-x\right)-\int_{0}^{x}\left(\frac{y+b}{y+c}+\frac{\left(y+a\right)}{y+d}+...+\frac{y+u}{y+v}\right)dy\leq 0$$