Skip to main content
1 of 8
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

I can explain how to find the worst case but it's a bit messy to continue.

First, note that if you interchange $a_k$ and $a_{k+1}$ then only the $k$-th term on the left side changes and the right side doesn't change at all. From this we can easily see that the worst order for a given set of values is $a_1\le a_2\le\cdots \le a_n$.

Now consider adjusting both $a_k$ and $a_{k+1}$ so that the right side remains unchanged. If $a_k\mapsto a_k+\epsilon$ then $a_{k+1}\mapsto a_{k+1} - \epsilon(a_{k+1}/a_{k})^2+O(\epsilon^2)$. On the left only the $k$-th and $(k+1)$-th terms change, and the change to the left side is $\Delta_k\epsilon+O(\epsilon^2)$, where $$ \Delta_k = -\frac{k}{(a_1+\cdots+a_{k})^2} + \frac{(k+1)((a_{k+1}/a_{k})^2-1)}{(a_1+\cdots+a_{k+1})^2}. $$ If we are sitting on the largest left side for given right side, we must have $\Delta_k=0$ for $1\le k\le n-1$. Starting arbitrarily with $a_1=1$, this defines the worst sequence exactly.

Unfortunately the equation $\Delta_k=0$ is a non-factorable quadratic in $a_{k+1}$ and it is hard to write the general solution. Apparently $a_2=3$ and $a_3=\frac{12}5+\frac25\sqrt{186}$.

Note that there is a single infinite sequence that works for all $n$.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147