# Euler-Maclaurin Summation

Using EM summation formula estimate $$\sum_{k=1}^n \sqrt k$$

up to the term involving $\frac{1}{\sqrt n}$

My attempt is $$\sum_{k=1}^n \sqrt k = \frac{2 \sqrt{n^3}}{3} -\frac{2}{3} + \frac 1 2 (\sqrt n -1)+ \frac{1}{24} (\frac{1}{\sqrt n} -1) + \int_1^n P_{2k+1}(x)f^{(2k+1)}(x)dx$$ I am not sure what can be said about the integral. Please tell me if I have made a mistake and how I can solve the integral? Have I stopped the summation at the right point?

• This was also discussed at this MSE link, which you may find enlightening. – Marko Riedel Jun 16 '15 at 19:35

Using the Euler-Maclaurin Sum Formula, we get $$\sum_{k=1}^n\sqrt{k}=\tfrac23n^{3/2}+\tfrac12n^{1/2}+\zeta(-\tfrac12)+\tfrac1{24}n^{-1/2}-\tfrac1{1920}n^{-5/2}+\tfrac1{9216}n^{-9/2}+O(n^{-13/2})$$ where the constant $$\zeta(-\frac12)=-0.20788622497735456602$$ is explained below.

By the Euler-Maclaurin Sum Formula, we have for $$\mathrm{Re}(s)\gt-1$$ $$\sum_{k=1}^nk^{-s}=\frac1{1-s}n^{1-s}+\frac12n^{-s}+\zeta_\ast(s)+O(n^{-s-1})\tag{1}$$ Define the sequence of functions $$\zeta_n(s)=\sum_{k=1}^nk^{-s}-\frac1{1-s}n^{1-s}-\frac12n^{-s}\tag{2}$$ For all $$n\ge1$$, $$\zeta_n(s)$$ is analytic. For $$\mathrm{Re}(s)\gt1$$, $$\lim\limits_{n\to\infty}\zeta_n(s)=\zeta(s)$$. Estimate $$(1)$$ says that on compact subsets of $$\{s\in\mathbb{C}\setminus\{1\}:\mathrm{Re(s)\gt-1}\}$$, $$\zeta_n(s)$$ converges uniformly. Thus, for $$s\in\mathbb{C}\setminus\{1\}$$ and $$\mathrm{Re}(s)\gt-1$$, $$\lim\limits_{n\to\infty}\zeta_n(s)$$ is analytic, so by analytic continuation, for $$\mathrm{Re}(s)\gt-1$$, $$\zeta_\ast(s)=\lim\limits_{n\to\infty}\zeta_n(s)=\zeta(s)\tag{3}$$

• @Robjon There were typos in the first non-enumerated equation ($x$ instead of $n$). I took the liberty of editing. I hope that you don't mind. I also edited my answer and would like to hear your thoughts on this expansion to $x^{-3/2}$. – Mark Viola Jun 17 '15 at 5:56
• Hi Rob. I hope that all is well. Just to clarify … Are you applying the AC to the punctured plane since $\zeta(s)$ is meromorphic with a single simple pole at $s=1$? – Mark Viola Nov 12 '18 at 18:34
• @MarkViola: yes. I guess I should have said "compact subsets of $\{s\in\mathbb{C}\setminus\{0\}:\mathrm{Re(s)\gt-1}\}$". I have updated the post. I missed that point because I was mainly interested in the leftward extension made possible by the Euler-Maclaurin Sum Formula. – robjohn Nov 12 '18 at 21:52
• You mean $\mathbb{C}\setminus \{1\}$, I believe. – Mark Viola Nov 12 '18 at 22:20
• (+1) for the very well-written solution! – Mark Viola Nov 13 '18 at 17:14

The correct expansion is given by

\begin{align} \sum_{i=1}^n f(i) &= \int_1^n f(x)dx + B_1 [f(n)+f(1)]\\\\ & + \sum_{k=1}^m \frac{B_{2k}}{(2k)!} \left(f^{(2k-1)}(n)-f^{(2k-1)}(1)\right)\\\\ & +\frac{1}{(2m+1)!}\int_1^n P_{2m+1}(x)f^{(2m+1)}(x) \end{align}

For $f(x)=x^{1/2}$ and $m=1$, we have

\begin{align} \sum_{i=1}^n\sqrt{i}&=\frac23 (n^{3/2}-1)+\frac12 (n^{1/2}+1)+\frac{1}{24}(n^{-1/2}-1)+\frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx\\\\ &=\frac23x^{3/2}+\frac12n^{1/2}+\left(-\frac23+\frac12-\frac{1}{24}\right)+\frac{1}{24}n^{-1/2}+\frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx \end{align}

The next task is to determine an estimate for the remainder $R$ where $R$ is the integral

$$R\equiv \frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx$$

We can find an estimate for the integral term

$$\int_1^n P_{3}(x)f^{(3)}(x)dx \tag1$$

using the well-known expression for the Bernoulli Polynomial

$$B_3(x)=x^3-\frac32 x^2+\frac12 x$$

We can easily verify that

$$-\frac{1}{12\sqrt{3}}<B_3(x)<\frac{1}{12\sqrt{3}}$$

for $x\in [0,1]$. Since $P_{2k+1}(x)=B_{2k+1}(x-\lfloor x\rfloor)$ then we see immediately that for $1<x<n$

$$-\frac{1}{12\sqrt{3}}< P_{3}(x) < \frac{1}{12\sqrt{3}}\tag 2$$

Now, we note that for $f(x)=x^{1/2}$, $f^{3}(x)=\frac38 x^{-5/2}>0$ for $x\in [1,n]$. Now, we use $(2)$ in the estimate of $(1)$ to reveal

\begin{align} -\frac{1}{48\sqrt{3}}\left(1-n^{-3/2}\right)<\int_1^n P_{3}(x)f^{(3)}(x)dx \le \frac{1}{48\sqrt{3}}\left(1-n^{-3/2}\right) \end{align}

Finally, we have the upper and lower bounds

$$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\sqrt{k}\le \frac23n^{3/2}+\frac12n^{1/2}+\left(-\frac{5}{24}+\frac{1}{288\sqrt{3}}\right)+\frac{1}{24}n^{-1/2}-\frac{1}{288\sqrt{3}}n^{-3/2}}$$

$$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\sqrt{k}\ge \frac23n^{3/2}+\frac12n^{1/2}+\left(-\frac{5}{24}-\frac{1}{288\sqrt{3}}\right)+\frac{1}{24}n^{-1/2}+\frac{1}{288\sqrt{3}}n^{-3/2}}$$

• The difference of the upper and lower bounds is $\frac1{144\sqrt3}$ which is bigger than $\frac1{24}n^{-1/2}$ for $n\gt108$. However, computing the actual values, both formulas on the right are over-estimates for the sum. – robjohn Jun 17 '15 at 11:27
• @robjohn Well, I found the error. I added $-2/3 +1/2-1/24$ and incorrectly got $-1/8$ (this is the reason to forgo doing arithmetic in my head late at night) edited version. The sum is actually $-5/24\approx. 0.20833$. The bounds are now correct. I do really want to thank you for all of the comments! – Mark Viola Jun 17 '15 at 16:35
• Now the bounds do bracket the sum. (+1) However for $n\gt108$, the difference in the bounds makes the last two terms insignificant. One point of the Euler-Maclaurin Sum Formula is that there is a constant that can replace $\left(-\frac5{24}+\frac1{288\sqrt3}\right)$ and $\left(-\frac5{24}-\frac1{288\sqrt3}\right)$. Even if it can't be determined symbolically, it can be evaluated numerically. Using the terms in my answer, and $n=1000$, we can compute $23$ places of the constant, since the next term is $-\frac{11}{163840}n^{-13/2}$. – robjohn Jun 17 '15 at 18:03
• @robjohn Yes, I understand that your approach is the better way. It is really pretty cool! But, rather than duplicate, I wanted to provide the OP with a more "brute force" way forward. – Mark Viola Jun 17 '15 at 18:09
• Yes, you are doing things using the integration by parts development. There is nothing wrong with that and it does give concrete bounds. Although I was concentrating on its numerical limitations, I didn't mean to deprecate your work (I did upvote :-). I simply wanted to point out that, in most cases, it is possible to compute the constant fairly accurately. – robjohn Jun 17 '15 at 18:34