2

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.

Mantrissa
  • 23

3 Answers3

3

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.

Guy
  • 8,857
  • 1
  • 28
  • 57
  • Doesn't a function of the form $\sum_{i=1}^{n}\frac{1}{c\sqrt{x}}$ scale as $\frac{H_n^{\frac{1}{2}}}{c}$ where $H_n$ is the Harmonic number of $n$? – Mantrissa Mar 14 '14 at 09:12
  • @Mantrissa you can check by bounding with the integral. You meant generalized harmonic number – Guy Mar 14 '14 at 09:14
  • Just ask wolfram alpha to do that sum for you. or I can right a proof? – Guy Mar 14 '14 at 09:14
  • Here's the WolframAlpha result: http://goo.gl/HbmbX5 – Mantrissa Mar 14 '14 at 09:15
  • So can we say this scales as $O(n^\frac{1}{2})$? $H_n$ blows up to infinity as $n \to \infty$ right? I'm not saying your wrong, just that this is a point of confusion for me. – Mantrissa Mar 14 '14 at 09:15
  • @Mantrissa yes. If the actual sums don't satisfy you I can prove that the sum lies between $\sqrt{x+1} -1$ and $\sqrt{x} - 1$. good enough? – Guy Mar 14 '14 at 09:17
  • Can we actually say something about the value of the smallest summand? And if you have a proof for that bound, that would be really neat. – Mantrissa Mar 14 '14 at 09:21
  • @Mantrissa yes we can say. that sum always lies between those two limits for any $n\gt 1$. – Guy Mar 14 '14 at 09:24
  • @Mantrissa even $\sqrt{n}$ blows up to $\infty$ as $n\to\infty$ – Guy Mar 14 '14 at 09:28
  • Just for the record, $H_n$ is $\Theta(\log(n))$ – Guy Mar 14 '14 at 09:28
  • Ah, I see now why you set $c = 2$ for $\sum_{i=1}^{n}\frac{1}{c\sqrt{x}}$. Nice. – Mantrissa Mar 14 '14 at 09:29
  • @Mantrissa thanks. :D any other constant would work though, since $\Theta(c\sqrt{x}) = \Theta(\sqrt{x})$ – Guy Mar 14 '14 at 09:30
  • $c=2$ just makes it as close to $\sqrt{x}$ as possible(at least for me) – Guy Mar 14 '14 at 09:30
  • Well, I meant that the bounds look pretty with $c = 2$ (oddly WolframAlpha times out with this integral). – Mantrissa Mar 14 '14 at 09:31
  • You're right that since $H_n \approx \Theta(\log(n))$ that we already have $O(n^\frac{1}{2})$ scaling. Can we say however that we have $\Theta(log(n)^\frac{1}{2})$ scaling for $\sum_{i=1}^{n}\frac{1}{c\sqrt{x}}$? – Mantrissa Mar 14 '14 at 09:33
  • @Mantrissa w|a is close to intelligent, not "human intelligent". We still have creativity. ;) – Guy Mar 14 '14 at 09:34
  • Yes, however both are larger than $\Theta(\sqrt{log(n)})$? – Mantrissa Mar 14 '14 at 09:37
  • @Mantrissa $\Theta(\log(n)^{1/2}) \lt \Theta(n^{1/2})$ And the summation here is always $\Theta(x^{1/2})$ no matter what $c$. To understand, see that we $c$ is a constant factor that can come out of the summation. – Guy Mar 14 '14 at 09:38
  • yes both are larger. typo – Guy Mar 14 '14 at 09:38
  • You mean that the sum here always has $\Theta(\log(n)^{1/2})$ and $O(n^\frac{1}{2})$ asymptotic scaling, or am I confused? – Mantrissa Mar 14 '14 at 09:41
  • @Mantrissa the sum always has $\Theta(n^{1/2})$ scaling, which is $\Omega(\log(n)^{1/2})$ – Guy Mar 14 '14 at 09:43
  • do you get it now? – Guy Mar 14 '14 at 09:43
  • $\Theta(n^{1/2})$ makes sense, since we know the sum is within a small constant of this. We also know that the floor is $\Omega(\log(n)^{1/2})$ within a constant. So this makes sense. I'm just unsure why we can't tighten Big Theta here to $\log(n)^{1/2}$? – Mantrissa Mar 14 '14 at 09:45
  • @Mantrissa $g(x)=\Theta(f(x))$ implies that $$cf(x)\lt g(x) \lt df(x)$$ for some $c,d\gt0$ once $x$ gets sufficiently large. Here you want to make $\sqrt{n} = \Theta(\log(n)^{1/2})$ but the square root function always grows faster than the logarithm, and so, the lower bound never gets satisfied, no matter what $c$ – Guy Mar 14 '14 at 09:49
  • 1
    Yup, makes sense. :) – Mantrissa Mar 14 '14 at 09:50
  • We can't have Big Theta, g(x) = Big Omega, f(x)? – Mantrissa Mar 14 '14 at 09:57
  • @Mantrissa what are your g and f? – Guy Mar 14 '14 at 10:05
  • This is guaranteed to be a stupid question, but why can't we say that, given: $cf(x)\lt g(x) \lt df(x)$, we can set $g(x) = f(x) = \sqrt{n} = \log(n)^{1/2}$? – Mantrissa Mar 14 '14 at 10:07
  • @Mantrissa if both $f$ and $g$ are $\sqrt{n}$ then where does your $\log$ come in. taking both $g$ and $f$ to be the same would make $\sqrt{x}=\Theta(\sqrt{x})$. Trivial. – Guy Mar 14 '14 at 10:10
  • I made a typo, I meant both are $\log(n)^{1/2}$? – Mantrissa Mar 14 '14 at 10:11
  • @Mantrissa yes. If both $f$ and $g$ are $\log(n)^{1/2}$ then we can write $g=\Theta(f)$. But you seem to have wandered off, how does this relate to the summation? – Guy Mar 14 '14 at 10:13
  • Well, we have an exact result for the summation, right? And this exact result is $H_n^\frac{1}{2}$. Now, we also know that the sum is within a small constant factor of $n^\frac{1}{2}$. So what's confusing to me is why we can't set Big Theta to the more precise expression for the sum's scaling $log(n)^\frac{1}{2}$ (given that $H_n \approx log(n)$)? – Mantrissa Mar 14 '14 at 10:17
  • @Mantrissa $H_n^{1/2} \ne \sqrt{H_n}$. The "exponent" of half is merely a notation. Btw, the second part is right. $H_n \approx \log(n) +\gamma$ to be more precise. – Guy Mar 14 '14 at 10:18
  • Oh, yikes yikes, its the order of the harmonic number. Everything makes sense now, I'm really glad you caught that! And the order doesn't seem like it would matter for the approximation $H_n \approx \log(n) +\gamma$ does it? – Mantrissa Mar 14 '14 at 10:22
  • @Mantrissa for that approximation, the order is fixed to be $1$ – Guy Mar 14 '14 at 10:25
  • I see, so we can't actually use that approximation where we have order $\frac{1}{2}$ as we do here. – Mantrissa Mar 14 '14 at 10:26
  • @Mantrissa no we can't. But we don't need to. $H_n^c$ can be derived using this same integral method. Euler's approximation of $H_n$ is just a special case of this(with $c=1$) – Guy Mar 14 '14 at 10:27
  • Ok, that's clear. Sorry about this, I tripped up on the notation. Thanks for your extensive help. – Mantrissa Mar 14 '14 at 10:28
  • If you integrate $1/x$ you get $\log(x)$. Same bounds as this. Using it we can say that $\log(n+1)\lt H_n \lt \log(n) + 1$. $\gamma$ is a tighter bound than $1$ – Guy Mar 14 '14 at 10:28
  • @Mantrissa happily. :) – Guy Mar 14 '14 at 10:29
1

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} $$

robjohn
  • 345,667
0

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$

5xum
  • 123,496
  • 6
  • 128
  • 204