maximizing a summation.

Question

Suppose we have $n$ nodes and $T_i(n):=$ number of visits to a node $i$ till time $n$. I have the following discrete summation, which I want to maximize: $$ \max_{\substack{ T_i(n) \\ 1 \leq i \leq k} } \sum_{i=1}^k \sum_{j=1}^{T_i(n)} \frac{1}{\sqrt{j} } \,\,\,\,\text{s.t.} \,\,\,\,\sum_{i=1}^k T_i(n) = n, $$ For instance for $k=2$, this would be maximizing $$\Bigg(1+\frac{1}{\sqrt{2}}+\cdots + \frac{1}{\sqrt{T_1(n)}}\Bigg) + \Bigg(1+\frac{1}{\sqrt{2}}+\cdots + \frac{1}{\sqrt{T_2(n)}}\Bigg)$$ I have the intuition that the above is maximized at $T_i(n) = \frac{n}{k},\,\forall \,i$. Is there any way to rigorously prove this for any finite $k$?

Answer 1

Yes, it appears that the maximum occurs when $T_i(n) \in \{\lfloor n/k \rfloor, \lceil n/k \rceil\}$ for all $i$. To prove this, you could show that any solution not of this form can be improved. For example, suppose $T_i(n) < \lfloor n/k \rfloor$ for some $i$, and modify the solution by increasing $T_i(n)$ by $1$ and decreasing some other $T_j(n) > \lfloor n/k \rfloor$ by $1$.