# Asymptotics for $p$-series with $p=1/2$

Reading solutions to a practice exam, and I come across this: $$O\left(\sum_{d \leq \sqrt{x}} {1 \over \sqrt{d}}\right) = O\left(x^{1/4}\right).$$ There are $O(\sqrt{x})$ terms in the sum, which are bounded between $x^{-1/4}$ and $1$. It looks like using the number of terms and the lower bound would give this estimate, but I don't see how that's valid.

• Hint: Approximate the sum from above and below by a suitable integral (the function will be $\frac{1}{\sqrt{t}}$). – André Nicolas Dec 19 '13 at 23:32

## 1 Answer

By comparison to integrals, $$2\sqrt{n+1}-2=\int_1^{n+1}\frac{\mathrm{d}x}{\sqrt{x}}\le\sum_{k=1}^n\frac1{\sqrt{k}}\le\int_0^n\frac{\mathrm{d}x}{\sqrt{x}}=2\sqrt{n}$$ So $$\sum_{k=1}^n\frac1{\sqrt{k}}=O(\sqrt{n})$$ plug in $n=\sqrt{d}$.

• If I wanted to generalize this to other $p \in (0,1)$, the result is $\sum_{k=1}^n k^{-p} = O(n^{1-p})$, right? – A l'Maeaux Dec 19 '13 at 23:41
• @Daniel: yes. The constant grows like $\frac1{1-p}$, so as $p\to1$, the constant gets very big. – robjohn Dec 19 '13 at 23:46