The bound can be improved to \[\frac{\sum_{i=1}^{n}\frac{1}{i}+\sum_{i=1}^{n^2}\frac{1}{i}}{2}.\] Let $S_n=1+a_1+...+a_n$ (let $S_0=1$). We want to prove that \[\sum_{i=1}^{n}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\leq\frac{\sum_{i=1}^{n}\frac{1}{i}+\sum_{i=1}^{n^2}\frac{1}{i}}{2}\] Fix some $m$. We will choose $m$ later on to be helpful. Note that using Cauchy Schwarz we have \[\Bigg(\sum_{i=1}^{m}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\Bigg)^2\leq\Bigg(\sum_{i=1}^{m}\bigg(\frac{1}{\sqrt{S_i}}\bigg)^2\Bigg)\Bigg(\sum_{i=1}^{m}\bigg(\frac{\sqrt{S_i-S_{i-1}}}{\sqrt{S_i}}\bigg)^2\Bigg)=\Bigg(\sum_{i=1}^{m}\frac{1}{S_i}\Bigg)\Bigg(\sum_{i=1}^{m}\frac{S_i-S_{i-1}}{S_i}\Bigg)\] But observe that because $a_1,...,a_n$ are positive integers then for each $i$, $S_i\geq i+1$ so \[\Bigg(\sum_{i=1}^{m}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\Bigg)^2\leq\Bigg(\sum_{i=1}^{m}\frac{1}{S_i}\Bigg)\Bigg(\sum_{i=1}^{m}\frac{S_i-S_{i-1}}{S_i}\Bigg)\leq\]\[ \leq\Bigg(\sum_{i=1}^{m}\frac{1}{i+1}\Bigg)\Bigg(\sum_{i=1}^{m}\bigg(\frac{1}{S_{i-1}+1}+\frac{1}{S_{i-1}+2}+...+\frac{1}{S_i}\bigg)\Bigg)=\Bigg(\sum_{i=1}^{m}\frac{1}{i+1}\Bigg)\Bigg(\sum_{i=2}^{S_m}\frac{1}{i}\Bigg)\] To get a nice bound for this, lets choose $m$ such that $S_1<S_2<...<S_m\leq n^2<S_{m+1}$ (and if there is no $k$ such that $S_k>n^2$ well then just take $m=n$ and continue). Observe that this gives us \[\Bigg(\sum_{i=1}^{m}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\Bigg)^2\leq\Bigg(\sum_{i=1}^{m}\frac{1}{i+1}\Bigg)\Bigg(\sum_{i=2}^{S_m}\frac{1}{i}\Bigg)\leq \Bigg(\sum_{i=1}^{m}\frac{1}{i+1}\Bigg)\Bigg(\sum_{i=2}^{n^2}\frac{1}{i}\Bigg)\]which, using the am-gm inequality, is smaller than \[\Bigg(\frac{\sum_{i=2}^{n}\frac{1}{i}+\sum_{i=2}^{n^2}\frac{1}{i}}{2}\Bigg)^2=\Bigg(\frac{\sum_{i=1}^{n}\frac{1}{i}+\sum_{i=1}^{n^2}\frac{1}{i}}{2}-1\Bigg)^2.\] Therefore, we got that \[\sum_{i=1}^{m}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\leq \frac{\sum_{i=1}^{n}\frac{1}{i}+\sum_{i=1}^{n^2}\frac{1}{i}}{2}-1.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(\dagger)\] So remember that $m$ is chosen such that $S_1<S_2<...<S_m\leq n^2<S_{m+1}$. We want to prove that \[\sum_{i=1}^{m}\frac{\sqrt{S_i-S_{i-1}}}{S_i}+\sum_{i=m+1}^{n}\frac{\sqrt{S_i-S_{i-1}}}{S_i}=\sum_{i=1}^{n}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\leq\frac{\sum_{i=1}^{n}\frac{1}{i}+\sum_{i=1}^{n^2}\frac{1}{i}}{2}\]so using what we got in $(\dagger)$, to get our desired inequality it is enough to prove that \[\sum_{i=m+1}^{n}\frac{\sqrt{S_i-S_{i-1}}}{S_i}\leq1.\](Remember that if there is no $k$ such that $S_k>n^2$ then this sum just doesn't exist and everything is ok) Observe that this is trivial because $\frac{\sqrt{S_i-S_{i-1}}}{S_i}\leq\frac{1}{\sqrt{S_i}}\leq \frac{1}{n}$ for $i=m+1,...,n$ because $n^2<S_{m+1}<S_{m+2}<...<S_n$.

Stars of Mathematics 2015 Senior Level #3 wrote: Let $n \in \mathbb{N}$ and let $a_1,a_2,...,a_n \in \mathbb{N}$. Prove that $$\sum_{k=1}^n\frac{\sqrt{a_k}}{1+a_1+a_2+...+a_k}<\sum_{k=1}^{n^2}\frac{1}{k}.$$ Another interesting, yet tricky inequality. Notice that for $n = 1$, the inequality is obvious, as we are asked to prove $\sqrt{a} < 1 + a$, which is straightforward. Now, we assume that $n \ge 2$. For simplicity, define $S_i = 1 + \sum_{k = 1}^i a_k$, and define $S_0 = 1$ as well. We want to prove that \[ \sum_{k = 1}^{n} \frac{\sqrt{S_{k} - S_{k - 1}}}{S_k} \le \sum_{k = 1}^{n^2} \frac{1}{k} \]Claim 01. [ Bound for $S_i$ ] For all $i \in \mathbb{N}_0$, we have $S_i \ge i + 1$. Proof. Notice that this is true for $i = 0$, and for $i \ge 1$, we have $S_i = 1 + \sum_{k = 1}^i a_k \ge 1 + i$ since $a_k \in \mathbb{N}$ by definition. Take the largest $m \in \mathbb{N}, m \le n$ such that $S_m \le n^2$. We'll now proceed to establish the following bounds. Claim 02. If $m < n$, then $\sum_{k = m + 1}^{n} \frac{\sqrt{S_k - S_{k - 1}}}{S_k} < 1$. Proof. To prove this, notice that \begin{align*} \sum_{k = m + 1}^{n} \frac{\sqrt{S_k - S_{k - 1}}}{S_k} &\le \sum_{k = m + 1}^{n} \frac{1}{\sqrt{S_k}} \\ &< \sum_{k = m + 1}^n \frac{1}{n} \\ &< \sum_{k = 1}^n \frac{1}{n} = 1 \end{align*} Claim 03. Otherwise, for $n \ge 2$, we have $\sum_{k = 1}^{m} \frac{\sqrt{S_k - S_{k - 1}}}{S_k} < \sum_{k = 2}^{n^2} \frac{1}{k} $ Proof. By Cauchy, we have \[ \sum_{k = 1}^m \frac{\sqrt{S_k - S_{k - 1}}}{S_k} \le \sqrt{\left( \sum_{k = 1}^m \frac{1}{S_k} \right) \left( \sum_{k = 1}^m \frac{S_k - S_{k - 1}}{S_k} \right)} \]From Claim 01, we have $\sum_{k = 1}^m \frac{1}{S_k} \le \sum_{k = 1}^m \frac{1}{k + 1}$ and the tricky bound, \begin{align*} \sum_{k = 1}^m \frac{S_k - S_{k - 1}}{S_k} &\le \sum_{k = 1}^m \left( \frac{1}{S_{k - 1} + 1} + \frac{1}{S_{k - 1} + 2} + \dots + \frac{1}{S_{k - 1} + (S_k - S_{k - 1})} \right) \\ &= \sum_{k = 2}^{S_m} \frac{1}{k} \end{align*}Hence, we conclude that since $n \ge 2$, then $n^2 > n + 1 \ge m + 1$, which gives us \begin{align*} \left( \sum_{k = 1}^m \frac{1}{S_k} \right) \left( \sum_{k = 1}^m \frac{S_k - S_{k - 1}}{S_k} \right) &\le \left( \sum_{k = 2}^{m + 1} \frac{1}{k} \right) \left( \sum_{k = 2}^{S_m} \frac{1}{k} \right) \\ &\le \left( \sum_{k = 2}^{m + 1} \frac{1}{k} \right) \left( \sum_{k = 2}^{n^2} \frac{1}{k} \right) \\ &< \left( \sum_{k = 2}^{n^2} \frac{1}{k} \right)^2 \end{align*} To finish this, just note that if $m = n$, then we are immediately done from the bound in Claim 03. Otherwise, \begin{align*} \sum_{k = 1}^n \frac{\sqrt{S_k - S_{k - 1}}}{S_k} &= \sum_{k = 1}^m \frac{\sqrt{S_k - S_{k - 1}}}{S_k} + \sum_{k = m + 1}^{n} \frac{\sqrt{S_k - S_{k - 1}}}{S_k} \\ &< \sum_{k = 2}^{n^2} \frac{1}{k} + 1 \\ &= \sum_{k = 1}^{n^2} \frac{1}{k} \end{align*} Motivational Remark. Another interesting inequality, with such a "contrived" statement I should say? The above solution relies greatly on algebraic manipulation, which is really non-trivial to find, at least for me (fail approach, and use that same idea to build up the above solution). First impression, is of course, as the title suggest, IMO SL 2001 A3 wrote: Let $x_1,x_2,\ldots,x_n$ be arbitrary real numbers. Prove the inequality \[ \frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2 + x_2^2} + \cdots + \frac{x_n}{1 + x_1^2 + \cdots + x_n^2} < \sqrt{n}. \] and this inequality itself is quite tricky. -- I and other TSTers attempted this problem and got this after like, 2 hours I guess, and laughed. Both of these inequality share a similar LHS but this problem shows a tighter bound in the RHS, which means the manipulation needed is not as "loose" as presented in the solution. Therefore, we try to consider \[ \frac{\sqrt{a_i}}{1 + a_1 + \dots + a_i} \le \left( \frac{1}{1 + a_1 + \dots + a_i} \right) \left( \frac{a_i}{1 + a_1 + \dots + a_i} \right) \]Quite inspired by IMO SL 2001 A3, we write $a_i = (1 + a_1 + \dots + a_i) - (1 + a_1 + \dots + a_{i - 1})$ instead, and therefore we would prefer to consider the substitution $S_i = 1 + a_1 + \dots + a_i$, which must satisfies the inequality $S_i \ge i + 1$. We now have LHS written as \[ \left( \sum_{k = 1}^n \frac{1}{S_k} \right) \left( \sum_{k = 1}^n \frac{S_{k} - S_{k - 1}}{S_k} \right) \]The most obvious approach is AM-GM this term, which doesn't work obviously like everyone would suspect. Therefore, we want to bound this term in a much smarter way. First of all, $\sum_{k = 1}^n \frac{1}{S_k}$ is easy to bound, as we already establish a bound of $S_i \ge i + 1$ for all $i \in \mathbb{N}$. The harder and non-obvious bound lies on $\sum_{k = 1}^n \frac{S_k - S_{k - 1}}{S_k}$. At first, I thought that to get the bound of this term, one must combine it with the previous term (maybe something like a tricky application of AM-GM perhaps), the thing is I don't think that this thing could be bound nicely like how $\sum_{k = 1}^n \frac{1}{S_k}$ could be bound.) However, at this point, writing the first few terms help: \[ \frac{S_1 - S_0}{S_1} + \frac{S_2 - S_1}{S_2} \le \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{S_2} \]where we try to bound this to expression of harmonic sum (because that's the RHS of the problem), and one can then notice that just like how we prove that $\sum_{i = 1}^{n} \frac{1}{i}$ diverges as $n \to \infty$, we can let \[ \frac{S_{i + 1} - S_i}{S_{i + 1}} \le \frac{1}{S_i + 1} + \frac{1}{S_i + 2} + \dots + \frac{1}{S_{i - 1} + (S_i - S_{i + 1})} \]which explain the whole bound really well, as we can establish the bound of \[ \sum_{k = 1}^n \frac{S_k - S_{k - 1}}{S_k} \le \sum_{k = 2}^{S_n} \frac{1}{k} \]We then want to somehow prove that \[ \left( \sum_{k = 2}^{n + 1} \frac{1}{k} \right) \left( \sum_{k = 2}^{S_n} \frac{1}{k} \right) \le \left( \sum_{k = 1}^{n^2} \frac{1}{k} \right)^2 \]For obvious reason one can really guess that this is not true as one can set $S_n \to \infty$, and the above inequality doesn't hold. Could this approach be fixed? If we have $S_m \le n^2$, by looking at RHS where we have $\sum_{k = 1}^{n^2} \frac{1}{k}$, then this inequality could be directly applied. This suggests us that we divide the original problem into $2$ sums before manipulating with CS. We'll now consider the case of summation from $1$ to $m$, and from $m + 1$ to $n$, assuming $n > m + 1$, otherwise, we could just apply our above argument directly. Now, for the summation from $1$ to $m$, we could apply our above inequality directly and for the other case, using our established bound of $S_i > n^2$, we could obtain $\sum_{k = m + 1}^{n} \frac{\sqrt{S_{k} - S_{k - 1}}}{S_k} < 1$, and we just need to prove our previous inequality with our bound set $S_n \le n^2$, however, this is pretty much obvious.

Did this a long time ago, was given during a test, but just recently found the post here. The bound can be further improved to $H_n = \sum_{i=1}^{n} \frac{1}{i}$. Define $S_i = a_1 + \dots + a_i$ and $S_0 = 0$. First we establish the following estimate: $S_n \ge n$ ($[\diamondsuit]$). This is true because $a_i \ge 1$ for each $i$. Now, we are ready to finish off. \begin{align*} \left( \sum_{k=1}^{n} \frac{\sqrt{a_k}}{1 + S_k} \right)^2 &\stackrel{\text{CS}}{\le} \left(\sum_{k=1}^n \frac{1}{k}\right)\left(\sum_{k=1}^n \frac{ka_k}{(1+S_k)^2}\right) = H_n \left(\sum_{k=1}^n \frac{ka_k}{(1+S_k)^2}\right) \\ &< H_n \left( \sum_{k=1}^n \frac{ka_k}{(1+S_k)(1+S_{k-1})} \right) = H_n \left( \sum_{k=1}^n \frac{k((1+S_k) - (1+S_{k-1}))}{(1+S_k)(1+S_{k-1})} \right) \\ &= H_n \left( \sum_{k=1}^n \left[ \frac{k}{1+S_{k-1}} - \frac{k}{1+S_k} \right] \right) \\ &= H_n \left( \left[ \frac{1}{1 + S_0} - \frac{1}{1 + S_1} \right] + \left[ \frac{2}{1 + S_1} - \frac{2}{1 + S_2} \right] + \dots + \left[ \frac{n}{1 + S_{n-1}} - \frac{n}{1 + S_n} \right] \right) \\ &= H_n \left( 1 - \frac{n}{1 + S_n} + \sum_{k=1}^{n-1} \frac{1}{1 + S_k} \right) < H_n \left( 1 + \sum_{k=1}^{n-1} \frac{1}{1 + S_k} \right) \\ &\stackrel{[\diamondsuit]}{\le} H_n \left( 1 + \sum_{k=1}^{n-1} \frac{1}{1 + (k)} \right) = H_n^2. \text{ } \square \end{align*} Remark. Using this approach, $a_i$ can be extended to real numbers not less than $1$.