# Show $\sum_{n\le x}\frac1{\sqrt n}=2\sqrt x+c+O(x^{-1/2})$

I am trying to show the asymptotic expansion for $$\sum_{n\le x}\frac1{\sqrt n}=2\sqrt x+\zeta(1/2)+O(x^{-1/2}).$$

(The exact identity of the zeta term is not important, it need only be some $c$.) To that end, I am attempting to prove the following slightly stronger theorem, which is supported by numerical evidence:

Let $F(x)=2\sqrt x-\sum_{n\le x}\frac1{\sqrt n}$. If $0<a\le b$, then $|F(a)-F(b)|\le\frac1{\sqrt a}$.

So far, I have only been able to show the weaker statement $|F(a)-F(b)|\le\dfrac2{\sqrt{\lfloor a\rfloor}}$, which is good enough for the asymptotic statement but can clearly be improved to work for all positive reals. My method:

$$\sum_{a<n\le b}\int_{n-1}^{n}(t^{-1/2}-n^{-1/2})\,dt=\sum_{a<n\le b}\left[2\sqrt n-2\sqrt{n-1}-\frac1{\sqrt n}\right]=F(\lfloor b\rfloor)-F(\lfloor a\rfloor)$$

Since the integrand is less than $\frac1{\sqrt{n-1}}-\frac1{\sqrt{n}}$ on its domain, we have:

$$|F(\lfloor b\rfloor)-F(\lfloor a\rfloor)|\le\sum_{a<n\le b}\frac1{\sqrt{n-1}}-\frac1{\sqrt{n}}=\frac1{\sqrt{\lfloor a\rfloor}}-\frac1{\sqrt{\lfloor b\rfloor}}$$

Finally, $F$ is differentiable on $(\lfloor x\rfloor,x)$ with $F'(y)=y^{-1/2}\le\lfloor x\rfloor^{-1/2}$, hence $|F(x)-F(\lfloor x\rfloor)|\le\frac1{\sqrt{\lfloor x\rfloor}}$. Putting it all together, we have

\begin{align} |F(b)-F(a)|&\le|F(a)-F(\lfloor a\rfloor)|+|F(b)-F(\lfloor b\rfloor)|+|F(\lfloor b\rfloor)-F(\lfloor a\rfloor)|\\ &\le\frac1{\sqrt{\lfloor a\rfloor}}+\frac1{\sqrt{\lfloor b\rfloor}}+\frac1{\sqrt{\lfloor a\rfloor}}-\frac1{\sqrt{\lfloor b\rfloor}}=\frac2{\sqrt{\lfloor a\rfloor}}. \end{align}

How can I avoid the use of $\frac1{\sqrt{\lfloor a\rfloor}}$, which is not even defined for $a<1$?

• Use Euler-Maclaurin. – Starfall May 6 '16 at 9:02
• Just by curiosity : why not to use the harmonic numbers ? – Claude Leibovici May 6 '16 at 9:07
• @ClaudeLeibovici Not sure what you mean. These are (generalized) harmonic numbers, but giving them a name doesn't make the proof any easier. – Mario Carneiro May 6 '16 at 9:09
• I was thinking about the asymptotics of the generalized harmonic numbers, But, again, this was just an idea coming to my mind. – Claude Leibovici May 6 '16 at 9:11
• @Starfall I don't have the full generality of Euler-Maclaurin available, so I'd have to prove it from scratch. If you know how to show this special case of it, then I'm all ears. – Mario Carneiro May 6 '16 at 9:12

Using Abel's summation formula we have $$\sum_{n\leq x}\frac{1}{\sqrt{n}}=\sum_{n\leq x}1\cdot\frac{1}{\sqrt{n}}=\sqrt{x}-\frac{\left\{ x\right\} }{\sqrt{x}}+\frac{1}{2}\int_{1}^{x}\frac{\left\lfloor t\right\rfloor }{t^{3/2}}dt=2\sqrt{x}-\frac{\left\{ x\right\} }{\sqrt{x}}-1-\frac{1}{2}\int_{1}^{x}\frac{\left\{ t\right\} }{t^{3/2}}dt$$ where $\left\lfloor t\right\rfloor$ is the floor function and $\left\{ t\right\}$ is the fractional part of $t$. So $$\left|F\left(b\right)-F\left(a\right)\right|=\left|\frac{\left\{ b\right\} }{\sqrt{b}}-\frac{\left\{ a\right\} }{\sqrt{a}}+\frac{1}{2}\int_{a}^{b}\frac{\left\{ t\right\} }{t^{3/2}}dt\right| \leq\left|\frac{\left\{ b\right\} }{\sqrt{b}}-\frac{\left\{ a\right\} }{\sqrt{a}}\right|+\frac{1}{\sqrt{a}}-\frac{1}{\sqrt{b}}\leq\frac{1}{\sqrt{a}}+\frac{\left\{ a\right\} }{\sqrt{a}}\leq\frac{2}{\sqrt{a}}$$ since $0\leq\left\{ t\right\} <1$. It is not the bound that we want but we have eliminated $1/\left\lfloor a\right\rfloor$.

• I'm confused by the application of Abel. The left side is clearly discontinuous at integer $x$, but the right side only has continuous functions $\sqrt x$ and $\int^x\dots$. – Mario Carneiro May 6 '16 at 10:02
• ...shouldn't that be $\lfloor x\rfloor/\sqrt x$ instead of $\sqrt x$? In fact, you proved that $F$ is continuous with this argument, which clearly isn't true. – Mario Carneiro May 6 '16 at 10:12
• @MarioCarneiro You're right, fixed. – Marco Cantarini May 6 '16 at 11:55
• I like this technique. You have essentially shown that it is better to consider $G(x)=F(x)-\frac{\{x\}}{\sqrt x}=\frac{x+\lfloor x\rfloor}{\sqrt x}+\sum_{n\le x}\frac1{\sqrt n}$, which unlike $F$ is continuous, and satisfies $|G(b)-G(a)|\le\frac1{\sqrt a}-\frac1{\sqrt b}$. The rest is just the cost of relating $G$ to $F$. – Mario Carneiro May 7 '16 at 0:44

This is a special case of the following theorem:

If $a:\Bbb R^{>0}\to\Bbb R^{\ge 0}$ is a decreasing function, and $A$ is an antiderivative of $a$, then letting $F(x)=A(x)-\sum_{n\le x}a(n)$, we have $$x\le y\implies |F(x)-F(y)|\le a(x).$$ Thus in particular, if $a\to 0$, then $F$ converges to some $c$, and $|F(x)-c|\le a(x)$.

The OP is the special case of this theorem for $a(x)=\frac1{\sqrt x}$ and $A(x)=2\sqrt x$.

Proof: Define the functions $$G_-(x)=F(x)-\{x\}a(x)=A(x)-\{x\}a(x)-\sum_{n\le x}a(n)$$ and $$G_+(x)=G_-(x)+a(x)=A(x)+(1-\{x\})a(x)-\sum_{n\le x}a(n).$$

We will show that $G_-$ is increasing and $G_+$ is decreasing, and $G_-(x)\le F(x)\le G_+(x)$. From this it follows that

$$F(y)-F(x)\le G_+(y)-G_-(x)\le G_+(x)-G_-(x)=a(x)$$ $$F(x)-F(y)\le G_+(x)-G_-(y)\le G_+(x)-G_-(x)=a(x)$$ so $|F(x)-F(y)|\le a(x)$.

Clearly $F(x)-G_-(x)=\{x\}a(x)\ge 0$, and $G_+(x)-F(x)=(1-\{x\})a(x)\ge 0$.

For fixed $k\in\Bbb N$, we note that $G_-(x)=A(x)-(x-k)a(x)-\sum_{n\le k}a(n)$ on $[k,k+1]$. On $[k,k+1)$ this is by definition, and at $k+1$ we have $$G_-(k+1)=A(k+1)-\sum_{n\le k+1}a(n)=A(k+1)-a(x)-\sum_{n\le k}a(n)$$. Thus given $k\le x\le y\le k+1$ we have \begin{align} G_-(y)-G_-(x)&=A(y)-A(x)-(y-k)a(y)+(x-k)a(x)\\ &\ge A(y)-A(x)-(y-x)a(y)\\ &=\int_x^y[a(t)-a(y)]\,dt\ge 0. \end{align}

Similarly, \begin{align} G_+(x)-G_+(y)&=A(x)-A(y)+(k+1-x)a(x)-(k+1-y)a(y)\\ &\ge A(x)-A(y)+(y-x)a(x)\\ &=\int_x^y[a(x)-a(t)]\,dt\ge 0. \end{align}

Thus $G_-$ is increasing and $G_+$ is decreasing on $[k,k+1]$, and by pasting together the intervals at the common points, we conclude that $G_-$ is increasing and $G_+$ is decreasing on $\Bbb R^+$.

• If the downvoter feels there is something wrong with this argument, please speak up. (Note that I wrote this as a roadmap for a formal proof, which was successfully completed, so it can't be too far off-base.) – Mario Carneiro May 10 '16 at 13:36