A sum that scales as the square root of the summands

Question

Is there some (edit! analytic) expression $h(x)$ such that the sum $$\sum_{i=1}^n h(i)$$ scales as $O\left(n^\frac{1}{2}\right)$?

Regarding the (40) comments under Sabyasachi's accepted answer: When you run a sum like $\sum_{i=1}^{n}\frac{1}{c\sqrt{x}}$ in WolframAlpha, the output should be interpreted as HarmonicNumber[n,1/2] (http://reference.wolfram.com/mathematica/ref/HarmonicNumber.html), where $r = \frac{1}{2}$ is the order of the harmonic number. $H_n^{\frac{1}{2}} \neq \sqrt{H_n}$! It's rather surprising that Sabyasachi and I got as far as we did before he noticed the error.

Answer 1

While 5xum's answer of the sum being $\sqrt{x}$ is certainly great, here is something easier to spot. Let $f(x)=\frac1{2\sqrt{x}}$. This can be bounded by the integral. The sum is $\Theta(\sqrt{n})$. Test results.

For $n=100$, sum is $9.24$
For n=1000, sum is $30.88$
For n=10000, sum is $99.26$

Pretty right?

---

Proof:

Obviously if $f$ is a monotonically decreasing function

$$\sum_{i=1}^nf(i) \lt \int_1^{n+1}f(x)\,dx$$

Similarly

$$\sum_{i=2}^nf(i)\gt\int_1^nf(x)\,dx()$$

or

$$\sum_{i=1}^nf(i)\gt f(1)+\int_1^nf(x)\,dx$$

Let $f(x)=\frac{1}{2\sqrt{x}}$ and we are done.

Answer 2

Why not? Take $h(1) = 1$, then define $$h(n) = n^{\frac12} - \sum_{i=1}^{n-1}h(i).$$

Then $$\sum_{i=1}^n h(i) = h(n) + \sum_{i=1}^{n-1}h(i) = n^{\frac12} - \sum_{i=1}^{n-1}h(i)+\sum_{i=1}^{n-1}h(i)=n^{\frac12}$$

This series is not just $O\left(n^\frac12\right)$, it is $n^\frac12$

Answer 3

The function $h(k)=\sqrt{k}-\sqrt{k-1}=\frac1{\sqrt{k}+\sqrt{k-1}}$ satisfies $$ \sum_{k=1}^nh(k)=\sqrt{n}\tag{1} $$

---

Analysis of $\ \displaystyle\mathbf{\sum_{k=1}^n\frac1{\sqrt{k}}}\,$:

Since $2\sqrt{k}\le\sqrt{k+1}+\sqrt{k}\le2\sqrt{k+1}$, we have $$ \frac12\sum_{k=1}^n\frac1{\sqrt{k+1}}\le\sum_{k=1}^n\frac1{\sqrt{k+1}+\sqrt{k}}\le\frac12\sum_{k=1}^n\frac1{\sqrt{k}}\tag{2} $$ Since $\frac1{\sqrt{k+1}+\sqrt{k}}=\sqrt{k+1}-\sqrt{k}$, we get $$ \begin{align} \sum_{k=1}^n\frac1{\sqrt{k+1}+\sqrt{k}} &=\sum_{k=1}^n\left(\sqrt{k+1}-\sqrt{k}\right)\\ &=\sqrt{n+1}-1\tag{3} \end{align} $$ Combining $(2)$ and $(3)$ yields $$ 2\sqrt{n+1}-2\le\sum_{k=1}^n\frac1{\sqrt{k}}\le2\sqrt{n}-1\tag{4} $$ Thus, $$ \sum_{k=1}^n\frac1{\sqrt{k}}=\Theta\left(\sqrt{n}\right)\tag{5} $$