Maximum of harmonic-type sum

Question

Suppose $ i_1,i_2, \dots, i_m $ is an increasing sequence of $ m $ positive integers from $ \{1, 2, \dots, n\} $, where $ n \geq m $. I am trying to determine how large the sum $$ \sum_{k=1}^{m-1} \frac{i_{k+1}-i_{k}}{i_{k+1}+i_{k}} $$ can be. My conjecture is that it is $ \Theta(\log(m)) $. For example, taking $ i_k = k $, we get the harmonic-type sum $ \sum_{k=1}^{m-1} \frac{1}{2k+1} $, which is $ \Theta(\log(m)) $. There are other choices of sequences that produce an even larger sum, but the asymptotic behavior is still $ \Theta(\log(m)) $. Any thoughts on how to tackle this problem?

Answer 1

If both $m$ and $n$ are fixed, then the optimal sequence approximates a geometric progression.

To see this, suppose that we have three consecutive terms $i_k = a, i_{k+1} = b, i_{k+2} = c$. While keeping $a$ and $c$ fixed, we want to choose the best value of $b$. Well, this only affects two terms: $$ \frac{b-a}{b+a} + \frac{c-b}{c+b} = \frac{2b(c-a)}{(b+a)(c+b)} = \frac{2(c-a)}{a + b + c + \frac{ac}{b}}. $$ The numerator here is positive and does not depend on $b$, so we want to make the denominator as small as possible. This requires minimizing $b + \frac{ac}{b}$; by the AM-GM inequality, $\frac{b + \frac{ac}{b}}{2} \ge \sqrt{ac}$ with equality attained only when $b = \frac{ac}{b} = \sqrt{ac}$, so that's how we want to choose $b$.

So, if we drop the requirement that $i_1, \dots, i_m$ are integers between $1$ and $n$, then in the optimal sequence, we have $i_k = \sqrt{i_{k-1} i_{k+1}}$ for each $k$, which means that $i_1, \dots, i_m$ is a geometric progression starting at $1$ and ending at $n$. (For the starting and ending points, we are just optimizing one term of the sum, and the optimal choice is to go as far towards the boundary as possible.)

This geometric progression must have $i_k = \alpha^{k-1}$, where $\alpha^{m-1} = n$, or $\alpha = n^{1/(m-1)}$. This makes $\frac{i_{k+1}-i_k}{i_{k+1}+i_k} = \frac{\alpha-1}{\alpha+1}$ for each term of the sum, so by comparing to the optimal sequence, we get the general upper bound: $$ \sum_{k=1}^{m-1} \frac{i_{k+1}-i_{k}}{i_{k+1}+i_{k}} \le \sum_{k=1}^{m-1} \frac{\alpha-1}{\alpha+1} = (m-1) \cdot \frac{n^{1/(m-1)} - 1}{n^{1/(m-1)} + 1}. $$ This bound can be achieved exactly if $i_1, \dots, i_m$ don't have to be integers, and also for particular values of $m,n$ where the geometric progression works out: for example, if $n = 2^{m-1}$, then we can set $i_k = 2^{k-1}$ and get a sum of $\frac{m-1}{3}$, matching this upper bound.

For other values of $m,n$, we might approach this bound by rounding the optimal sequence to the nearest integer values; for example, when $m=n$, we have $(m-1) \frac{m^{1/(m-1)}-1}{m^{1/(m-1)}+1} \sim \frac12 \log m$, which matches the behavior of the optimal (and only possible) integer sequence $i_k = k$ up to lower-order terms.