Is it true that $ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $?

Question

Is the following true?
$$ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $$

Answer 1

No. Break the interval $[1,T]$ up into $\sqrt T$ intervals of size $\sqrt T$. Then for each interval $k$ we have:

$$\sum_{i=k\sqrt T+1}^{(k+1)\sqrt T}\frac {T-t}{t+\sqrt{T-t}}=\sqrt T\Theta(\frac {T-k\sqrt T}{k\sqrt T+\sqrt{T-k\sqrt T}})=\Theta(\frac T {k+1})$$ Where constants hidden in $\Theta$ can be chosen uniformly in $k$. Summing over $k$ from $0$ to $\sqrt T-1$ leads to: $$\text{Your sum}=\Theta(T\log T).$$

Answer 2

The idea is similar to A.S.' answer, I just want to make the calculation more explicit and clearer.

In fact we can show that $$\limsup_{T \to \infty} \frac{1}{T}\sum_{t = 1}^T \frac{T - t}{t + \sqrt{T - t}} = \infty, \tag{$*$}$$ thus the conjecture is false.

We prove $(*)$ by considering a subsequence of $\{1, 2, \ldots\}$. Let $T = n^2, n = 1, 2, \ldots$. We then partition the summation in $(*)$ into each sub-block $\{in + 1, \ldots, (i + 1)n\}$ of $\{1, 2, \ldots, n^2\}$ for $i = 0, 1, \ldots, n - 1$. Since the summand $\frac{T - t}{t + \sqrt{T - t}}$ is a nonincreasing function of $t$, it follows that \begin{align*} & \frac{1}{T}\sum_{t = 1}^T \frac{T - t}{t + \sqrt{T - t}} \\ = & \frac{1}{n^2}\sum_{i = 0}^{n - 1}\sum_{k = in + 1}^{(i + 1)n} \frac{n^2 - k}{k + \sqrt{n^2 - k}} \\ \geq & \frac{1}{n^2}\sum_{i = 0}^{n - 1}\frac{n^2 - (i + 1)n}{(i + 1)n + \sqrt{n^2 - (i + 1)n}} \times n \\ = & \sum_{i = 0}^{n - 1}\frac{1 - \frac{i + 1}{n}}{\frac{i + 1}{n} + \frac{1}{n}\sqrt{1 - \frac{i + 1}{n}}} \times \frac{1}{n} \\ \geq & \sum_{i = 0}^{n - 1}\frac{1 - \frac{i + 1}{n}}{\frac{i + 1}{n} + \frac{1}{n}} \times \frac{1}{n} \\ \geq & \sum_{i = 0}^{n - 1}\frac{1 - \frac{i + 1}{n}}{\frac{i + 1}{n} + \frac{i + 1}{n}} \times \frac{1}{n} \\ = & \frac{1}{2}\sum_{i = 0}^{n - 1}\frac{1 - \frac{i + 1}{n}}{\frac{i + 1}{n}} \times \frac{1}{n} \\ \geq & \frac{1}{2}\int_{\frac{1}{n}}^1 \left[\frac{1}{x} - 1\right] dx \\ = & \frac{1}{2}\log n - \frac{1}{2} + \frac{1}{2n}. \end{align*} The last expression tends to $\infty$ as $n \to \infty$. Therefore, $(*)$ holds.