Skip to main content
2 of 2
deleted 20 characters in body
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Proving a sum to be sublinear in growth

Suppose that $\alpha \in (0,1)$. The goal is to prove that the following sum is of $o(T)$ (or, if possible, give a more accurate growth rate, e.g. $O(T^{1-\alpha})$ or something like that): $$ \sum_{t=1}^T \prod_{i=0}^{\lfloor\sqrt{t}\rfloor-1}(1 - (t-i)^{-\alpha}).$$ It is also easy to see that the growth rate of the sum below is higher than the one above. So proving sub-linearity of the sum below also is enough: $$ \sum_{t=1}^T (1 - t^{-\alpha})^{\sqrt{t}}.$$