# Find the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct in $\{1,2,…,n\}$

What is the tight upper bound of $$\sum_{i=1}^n \frac{i}{i+x_i}$$, where the $$x_i$$'s are distinct integers in $$\{1,2,...,n\}$$?

• Are you asking for the maximum of $f:S_{n}\rightarrow\mathbb{R}:\sigma\mapsto\sum_{i=1}^{n}\frac{i}{i+\sigma(i)}$? – Nicéphore Bayekula Nov 1 '18 at 9:08

I doubt that there is an exact formula for this maximum, and unfortunately Wolfgang's guess is incorrect. Indeed, let $$a_n = \mathrm{max}_{\sigma \in \mathfrak{S}_n} \sum_{i=1}^n \frac{i}{i + \sigma(i)}.$$ Then by considering the standard embedding $$\mathfrak{S}_n \times \mathfrak{S}_m \hookrightarrow \mathfrak{S}_{n+m}$$, one checks that $$a_{n+m} \geq a_n + a_m,$$ so that the sequence $$\frac{a_n}{n}$$ converges to the number $$c = \mathrm{sup}_n \frac{a_n}{n} \in [\frac{1}{2},1]$$. Now, I claim that $$c > \frac{1}{2}$$, so that neither $$\mathrm{id}$$ nor $$(n, 1, 2,...,n-1)$$ grant the maximum when $$n$$ is large.

For $$r = r_n = \lfloor \alpha n \rfloor$$ with $$\alpha \in ]0,1[$$, let us consider the cycle $$(n-r+1,n-r+2,...,n-1,n,1,2,...,n-r)$$. Then we get \begin{align*} c &\geq \lim_n \frac{1}{n} \left( \sum_{j=1}^r \frac{j}{n-r+2j} + \sum_{j=r+1}^n \frac{j}{2j-r} \right) \\ &= \frac{1}{2} + \frac{\alpha}{4} \log \left( \frac{2-\alpha}{\alpha} \right) - \frac{1-\alpha}{4} \log \left( \frac{1+\alpha}{1-\alpha} \right) . \end{align*} This is $$> \frac{1}{2}$$ for $$\alpha \in ]0, \frac{1}{2}[$$. The maximum is around $$\alpha = 0.14868$$, where the bound is $$c >0.529$$.

• Here are the first few maxima: $([1], 1/2)$, $([1, 2], 1), ([2, 1], 1)$, $([3, 1, 2], 91/60)$, $([4, 1, 2, 3], 214/105)$, $([5, 1, 2, 3, 4], 1613/630)$, $([6, 1, 2, 3, 4, 5], 10679/3465)$, $([7, 1, 2, 3, 4, 5, 6], 1298221/360360)$, $([8, 7, 1, 2, 3, 4, 5, 6], 3469/840)$, $([9, 8, 1, 2, 3, 4, 5, 6, 7], 2609/560)$, $([10, 9, 1, 2, 3, 4, 5, 6, 7, 8], 287579/55440)$ – Martin Rubey Nov 2 '18 at 16:17
• In fact, if this pattern persists, then the maximum would be $\frac{1}{4} \, r {\left(H_{n - r/2} - H_{r/2} - 2\right)} + \frac{1}{2} \, n + \frac{r(r+1)}{2 \, {\left(n + 1\right)}}$ for some $r$, where $H_k$ is the harmonic number. – Martin Rubey Nov 2 '18 at 16:39

Most surely, (see bottom) Initially I had thought $$max=\frac1{1+n}+\sum_{i=2}^n \frac i{i+(i-1)},$$ but my proof below is still somewhat incomplete...

If the $$x_i$$ are a permutation $$\pi$$ of $$\{1,2,...,n\}$$, let $$y_i:=\pi^{-1}(i)$$ Then we have $$\sum_{i=1}^n \frac{i}{i+x_i}=n-\sum_{i=1}^n \frac{x_i}{i+x_i}=n-\sum_{j=1}^n \frac{j}{y_j+j},$$ so the sums come in pairs, and if $$\pi$$ yields a maximum, then $$\pi^{-1}$$ will yield a minimum.

I'd like to show that the maximum is attained for the permutation $${\pi:=(n,1,2,...,n-1)}$$.

Now, for $$i>1$$ and $$k, $$\frac1{1+n}+\frac i{i+k}>\frac 1{1+k}+\frac i{i+n}$$because $$LHS-RHS=\frac{(i - 1) (n-k) (k n - i)}{(1+n) (i + k)(1+k) (i + n)}>0.$$ So we must have $$x_1=n$$ for a maximal permutation.

Generally, $$\frac j{j+a}+\frac k{k+b}-\left(\frac j{j+b}+\frac k{k+a}\right) =\frac{(b-a)(k-j)(jk-ab)}{(j+a) (k+b) (j+b)(k+a)}.$$ Thus if for $$j\ge2$$ we put $$x_j=j-1$$, the above difference (with putting $$a=x_j, b=x_k$$) is always positive. This proves that $$\pi$$ does strictly better than with any involution applied to it, which gives a strong evidence in favor of $$\pi$$.
But the problem remains that we cannot conclude from there for any combination of involutions because of the factor $$(jk-ab)$$ which might become negative at some point.

EDIT after js21's answer: That shot was too quick. It looks in fact like the maximum is attained for the permutation $$\color{red}{\pi_k=[n,n-1,...,n-k+1,1,2,...,n-k]}$$ with $$k\approx \dfrac n{6.3032}$$, thus linear in $$n$$. This is very precise: for $$n<1,000,000$$, the optimal $$k$$ always seems to be within a range $$\pm1$$ of this fraction, even for small $$n$$.

• How can you check that the maximum for such a large $n$ is of the given form? Besides, I think that @js21 considered a different permutation (which yields a large value, but not the maximum)... – Martin Rubey Nov 2 '18 at 22:08
• @MartinRubey Of course, like for most conjectures, there is a certain amount of educated guess involved. I have not checked millions of sums, I just say "it looks like", but I don't claim... One of my assumptions is a kind of monotonicity, which seems highly plausible: if for a fixed $n$, we take $\pi_k:=[n,n-1,...,n-k+1,1,2,...,n-k]$, then there is a $k$ such that $f(\pi_1)<\cdots<f(\pi_k)>f(\pi_{k+1}>\cdots$. And the first $\pi_k$ seem to be the best candidates, so... My "indeed" referred rather to your first comment there than to js21's permutations. :) In any case, we must have $x_1=n$. – Wolfgang Nov 3 '18 at 13:10
• OK, I just thought you had some way to check that the general form I mentioned in the comment was correct. By the way, the poset of permutations ordered by $f$ is quite interesting! – Martin Rubey Nov 3 '18 at 13:25
• Another comment: if I made no mistake, given the conjectural form, I think that $k\simeq c\cdot n$ should be such that $c$ is the zero of $(c-2)\ln(\frac{c}{2}-1) + 2(2c-3)(c-1)$. So, $1/c=6.303250770424045$ as you write. – Martin Rubey Nov 3 '18 at 13:31
• @MartinRubey That sounds good. How did you come up with that? I suppose by solving $f(\pi_k)=f(\pi_{k+1})$ for big n, using asymptotics of the harmonic series? – Wolfgang Nov 3 '18 at 16:46