An inequality on sequences with each term dividing sum of two neighbouring terms

Positive integers $x_1, x_2, \dots, x_n$ ($n \ge 4$) are arranged in a circle such that each $x_i$ divides the sum of the neighbors; that is $$\frac{x_{i-1}+x_{i+1}}{x_i} = k_i $$ is an integer for each $i$, where $x_0 = x_n$, $x_{n+1} = x_1$. Prove that $$ 2n \le k_1 + k_2 + \dots + k_n < 3n. $$

This is a problem from some olympiad but I don't remember. What I did was like this :

Let $x_1$ be the smallest. Then obviously, $k_1\ge 2$. I tried to proceed inductively, but then I have no idea. I know it is not something useful, but I lack in any kind of idea. If I try induction, three new terms come replacing three previous terms. Which seems complicated and I can't do anything with it.

Sorry for such a bad try, but I seriously don't have any idea about it. Maybe something ingenious is required here. I hope someone can help. Thanks.

EDIT : Removed meaningless ramblings of mine. Apologies.

Solution 1:

The lower bound only:

Update: I just realized there is an easier argument. The terms in the sum $\sum_i x_{i+1}/x_i$ are just the reciprocals of the terms in the sum $\sum_i x_{i-1}/x_i$. Therefore, our sum $\sum_i k_i$ can be expressed as the sum of $n$ terms of the form $y+{1\over y}.$ Since $y+{1\over y}\geq 2$ for all positive $y$, we get $\sum_i k_i\geq 2n.$

This is exercise 5.7(a) from The Cauchy-Schwarz Master Class by J. Michael Steele. Let $y_i$ be your values $x_i$ only put in order so that $y_1\leq y_2\leq \cdots \leq y_n$. Then the reciprocals are in the opposite order $1/y_n\leq 1/y_{n-1}\leq \cdots \leq 1/y_1$. The lower bound in the rearrangement inequality says that $$n={y_1\over y_1}+{y_2\over y_2}+\cdots+{y_n\over y_n} \leq {y_1\over y_{\sigma(1)}}+{y_2\over y_{\sigma(2)}}+\cdots +{y_n\over y_{\sigma(n)}},$$ for any permutation $\sigma$.

For the appropriate permuations $\sigma$ we get $n\leq \sum_i x_{i-1}/x_{i}$ and $n\leq \sum_i x_{i+1}/x_{i}$ where the index runs cyclically: $\dots,n,1,2,\dots,n-1,n,1,\dots$. Adding these together gives $$2n\leq \sum_i {x_{i-1}+x_{i+1}\over x_i}.$$

Solution 2:

I'm going to reformulate the problem in a slightly more convenient way (I rename $k_i-2$ as $k_i$).

Consider a sequence $\{(x_i,k_i)\}_{i=1}^n\subset \mathbb{R}^+\times \mathbb{Z}$ such that $$ x_ik_i=(x_{i+1}-x_i)-(x_{i}-x_{i-1}). $$ Prove that $0\leq \sum_{i=1}^nk_i<n.$

Upper Bound:

Since $x_i(k_i+2)=x_{i+1}+x_{i-1}>0$, each $k_i\geq -1$. Also notice that $\sum_{i=1}^n x_ik_i=0$. If $k_i=0$ for all $i$, we are done. Thus we may assume $k_1=-1$ without loss of generality.

Induct on $n$, starting at $n=2$. In this case we have $$ \{(2x,-1),(x,2)\},\qquad \mbox{ and }\sum_{i=1}^2 k_i=1<2. $$

Now consider the sequence $\{(x_i,k_i)\}_{i=1}^n$ where $k_1=-1$. Then $x_1=x_2+x_n$; substituting into the $i=2$ and $i=n$ equations yields the sequence $$ \{(x_i',k_i')\}_{i'=1}^{n-1}=\{(x_2,k_2-1),(x_3,k_3),\cdots,(x_{n-1},k_{n-1}),(x_n,k_n-1)\}. $$ Observe that the new sequence is still valid. Applying the inductive hypothesis, $$ \sum_{i=1}^n k_n = (-1) + \sum_{i=2}^n k_n = 1 + \sum_{i=1}^{n-1} k_n' < 1 + (n-1) = n. $$

Lower Bound: Apply AM-GM as follows. $$ \sum_{i=1}^nk_i=\sum_{i=1}^n\left(\frac{x_i}{x_{i+1}}+\frac{x_{i+1}}{x_{i}}-2\right)\geq 0. $$

Solution 3:

The lower bound is a simple consequence of the rearrangement inequality, as Byron pointed out. So I will focus on the upper bound.

We will proceed by induction. Call sum of k's as S.

Base case: For n = 2, suppose the numbers are a and b. If a = b, then S = 2 + 2 = 4. Else, let a < b. b|2a, so b = 2a. This gives S = 4 + 1 = 5 < a * 3 = 6. So base case is all good.

Induction case: Suppose the condition holds till n. For the n+1 case, consider the largest element in the array. If there are multiple such elements, take any one of them. Call this m. Let the elements on either side of this maximum be a and b. If either a or b is m, then two things can happen:

1) Either the other one is also m 2) Or the other one is 0

0 is ruled out by the wording of the question (anyway, 0 does not divide sum of positive numbers). So both have to be m. Continuing this way, all elements have to be same. The condition is clearly satisfied in this case.

So we are left with the case where both a and b are less than m. So their sum is less than 2m. In other words, m = a + b. Suppose the elements beyond a and b are respectively c and d. In other words, the part of the array around a + b looks like this:

...c, a, a+b, b, d...

a|(a+b+c), so a|(b+c). Similarly, b|(a+b+d). So b|(a+d).

What this means is that we can go from this array to another valid array with (a+b) removed:

...c, a, b, d...

Now, what is the contribution to S by this a+b? 1 from a+b = 1(a+b). Let a+d=pb. Then (a+b+d)=(p+1)b. Similarly, let b+c=qa. Then (a+b+c)=(q+1)a.

So 1 is added to the k's corresponding to each of a and b by the addition of a+b. This is in addition to the 1 in the k corresponding to (a+b) itself.

So total increase = 3.

Because of this, by induction, if S for n < 3n, then S for (n+1) < 3n + 3 = 3(n+1).

Solution 4:

Lower bound: Am-Gm inequality: $\displaystyle \sum\limits_{i=1}^n k_i = \sum\limits_{i=1}^n {\dfrac{x_i}{x_{i+1}}}+\dfrac{x_{i+1}}{x_i} \ge 2n$

Upper bound: We can show by strong induction on $n$ that, $\displaystyle \sum\limits_{i=1}^n k_i < 3n$

Suppose, $\exists \,n_0 (\ge 2)$, such that $\displaystyle \sum\limits_{i=1}^{n_0} k_i < 3n_0$.

For $n > n_0$, we may assume that not all $x_i$'s are equal (in which case $\displaystyle \sum\limits_{i=1}^n k_i = 2n$), so that there is a $j$ for which $x_j \ge x_{j-1}$ and $x_j \ge x_{j+1}$, with a strict inequality in atleast one of these two.

So, $2x_j > x_{j-1} + x_{j+1}$, and hence $k_j = 1$.

Thus, the cyclic arrangement with $x_j$ removed also satisfies the given conditions, with $k_{j-1}$ and $k_{j+1}$ both decreased by $1$, and $k_j$ removed.

Since, the sum of resulting $n-1$, $k_i$'s does not exceed $3(n-1)$ (by, induction hypothesis), $\implies \displaystyle \sum\limits_{i=1}^n k_i < 3n$.

We need to check the base case $n_0$.

The establish the base case, $n_0 = 4$, we make an argument similar as above and assume not all $x_1,x_2,x_3,x_4$ are equal and wlog that $2x_4 > x_1 + x_3$, implying $k_4 = 1$. Which brings it down to $k_1' = \dfrac{x_2 + x_3}{x_1}$, $k_2 = \dfrac{x_1+x_3}{x_2}$ and $k_3' = \dfrac{x_1+x_2}{x_3}$. Again if we assume not all $x_1,x_2,x_3$ are equal (equality leads to $k_1'+k_2+k_3' = 6$), that is wlog $2x_3 > x_1+x_2$, which leaves us to prove $\dfrac{2x_1}{x_2}+\dfrac{2x_2}{x_1} < 6$, where $p=\dfrac{2x_1}{x_2},q=\dfrac{2x_2}{x_1}$ are integers.

Hence, $p+\dfrac{4}{p} = 4,5 < 6$ depending on $p=1,2,4$. Thus the base case holds.