<s>[INST] Prove that a certain series grows as $O(\log n)$ The problem below is an exercise that came up during self-study. I cannot even easily convince myself of its truth.
Problem: There is a sequence of reals $1 = a_1 \leq a_2 \leq \ldots \leq a_n$ satisfying $a_{i+1}-a_i \leq \sqrt{a_i}$ for all $1 \leq i < n$. Prove that $$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \leq O(\log n).$$
As a first step, letting $f(n)$ denote the LHS in the desired inequality, we can write $$f(n) = \sum_{i=1}^{n-1} \frac{1}{\sqrt{a_i}}.$$ My next thought is to show that this is less than a series that we know grows as $O(\log n)$, maybe the harmonic series, but I am stuck at this point.
 [/INST] Note that $$a_{k+1} \le a_k+\sqrt{a_k} < a_k + \sqrt{a_k}+\tfrac{1}{4} = \left(\sqrt{a_k}+\tfrac{1}{2}\right)^2,$$ i.e. $\sqrt{a_{k+1}} < \sqrt{a_k}+\tfrac{1}{2}$ for all $k$. Hence, we can use induction to show that $\sqrt{a_n} \le \tfrac{n+1}{2}$ for all $n$. 
Then for all $n$, we have: 
\begin{align*}
\sum_{k = 1}^{n-1}\dfrac{a_{k+1}-a_k}{a_k} &\le \sum_{k = 1}^{n-1}\dfrac{a_{k+1}-a_k}{\left(\sqrt{a_{k+1}}-\tfrac{1}{2}\right)^2} & \text{since} \ \sqrt{a_{k+1}} < \sqrt{a_k}+\tfrac{1}{2}
\\
&= \sum_{k = 1}^{n-1}\int_{a_k}^{a_{k+1}}\dfrac{1}{\left(\sqrt{a_{k+1}}-\tfrac{1}{2}\right)^2}\,dx 
\\
&\le \sum_{k = 1}^{n-1}\int_{a_k}^{a_{k+1}}\dfrac{1}{\left(\sqrt{x}-\tfrac{1}{2}\right)^2}\,dx & \text{since} \ \dfrac{1}{(\sqrt{x}-\tfrac{1}{2})^2} \ \text{is decreasing}
\\
&= \int_{1}^{a_n}\dfrac{1}{\left(\sqrt{x}-\tfrac{1}{2}\right)^2}\,dx 
\\
&= \left[2\log\left(2\sqrt{x}-1\right) - \dfrac{2}{2\sqrt{x}-1}\right]_{1}^{a_n}
\\
&= 2\log\left(2\sqrt{a_n}-1\right) - \dfrac{2}{2\sqrt{a_n}-1} + 2 
\\
&\le 2\log\left(2\sqrt{a_n}-1\right)+2 
\\
&\le 2 \log n + 2. & \text{since} \ \sqrt{a_n} \le \tfrac{n+1}{2}
\end{align*}
Therefore, $\displaystyle\sum_{k = 1}^{n-1}\dfrac{a_{k+1}-a_k}{a_k} = O(\log n)$ as desired.
</s>