¿Es cierto que $ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $ ?

Question

¿Es cierto lo siguiente?
$$ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $$

Answer 1

No. Romper el intervalo $[1,T]$ en $\sqrt T$ intervalos de tamaño $\sqrt T$ . Entonces, para cada intervalo $k$ que tenemos:

$$\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})$$ Donde las constantes ocultas en $\Theta$ puede elegirse uniformemente en $k$ . La suma de $k$ de $0$ a $\sqrt T-1$ conduce a: $$\text{Your sum}=\Theta(T\log T).$$

Answer 2

La idea es similar a la respuesta de A.S., sólo quiero que el cálculo sea más explícito y claro.

De hecho, podemos demostrar que $$\limsup_{T \to \infty} \frac{1}{T}\sum_{t = 1}^T \frac{T - t}{t + \sqrt{T - t}} = \infty, \tag{$ * $}$$ por lo que la conjetura es falsa.

Demostramos $(*)$ considerando una subsecuencia de $\{1, 2, \ldots\}$ . Dejemos que $T = n^2, n = 1, 2, \ldots$ . A continuación, dividimos la suma en $(*)$ en cada sub-bloque $\{in + 1, \ldots, (i + 1)n\}$ de $\{1, 2, \ldots, n^2\}$ para $i = 0, 1, \ldots, n - 1$ . Dado que el sumando $\frac{T - t}{t + \sqrt{T - t}}$ es una función no creciente de $t$ se deduce que \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*} La última expresión tiende a $\infty$ como $n \to \infty$ . Por lo tanto, $(*)$ se mantiene.