"Difference Equations" by Walter G. Kelley and Allan C. Peterson, 2nd Edition, gives an example on how to approximate $\sum_{k=1}^n{k^{1/2}}$ using integrals and Bernoulli numbers.

I'm interested in nesting summations and using integrals to approximate them. So I cooked up a relatively simple example:

$$\sum_{j=0}^n{\sum_{k=0}^j{c^j k^{1/2}}}$$

I'm mainly interested in knowing how to include an estimate from nested integrals. The book gives the Euler summation formula:

$$\displaystyle\sum_{k=1}^n{f(k)} = $$

$$\displaystyle\int_1^n{f(t)dt}+\frac{f(n)+f(1)}{2} + $$ $$\displaystyle\sum_{i=1}^m{\frac{B_{2i}}{(2i)!}\left(f^{(2i-1)}(n)-f^{(2i-1)}(1)\right)} - $$ $$\displaystyle\frac{1}{(2m)!}\int_1^n{f^{(2m)}(t)B_{2m}(t-\lfloor t \rfloor)dt}$$

where $B_i$ represents the $i$th Bernoulli number. This formula allows one to estimate a summation by using integrals and Bernoulli numbers. More information can also be found here, in Wikipedia's entry on it.

I'm gussing what I can do is start with $\sum_j \sum_k f(j,k)$ and plug in $\sum_k f(j,k)$ into the Euler summation formula to get half of a big formula. Then plug that in, along with $\sum_j$, into a second Euler summation formula.


Can someone please show me how I can approximate the solutions by using Euler summations? It would help me a great deal, so I'd be very greatful! Thanks for reading.


2 Answers 2


Your sum is $$\sum_{j=0}^nc^j\sum_{k=0}^j\sqrt k$$ Euler summation on the inner sum should give you something like $$\sum_{k=0}^j\sqrt k=(2/3)j^{3/2}+{\rm\ lower\ terms}$$ So now you're after $$\sum_{j=0}^nj^{3/2}c^j$$ Euler summation will compare this to $$\int_0^nt^{3/2}c^t\,dt$$ which looks to me like an "incomplete Gamma function," q.v.

  • $\begingroup$ Also, if $0 < c < 1$ is fixed and $n \to \infty$ then that incomplete gamma function should be pretty well approximated by an ordinary gamma function. $\endgroup$ Nov 7, 2011 at 3:50
  • $\begingroup$ @Gerry Myerson: I'm interested in knowing the error bounds for these functions, though. I'd really like to see how the error changes if I plug in values for the second integration. $\endgroup$
    – Matt Groff
    Nov 7, 2011 at 18:11
  • $\begingroup$ Then I guess you'll have to carry out the Euler summation in more detail. $\endgroup$ Nov 7, 2011 at 21:53
  • 1
    $\begingroup$ @GerryMyerson. The simplest for of Euler-MacLaurin summation gives a monster $\endgroup$ Apr 18 at 14:15

As I commented, the simplest for of Euler-MacLaurin summation gives a monster (I refuse to type it - too long).

Trying for $c=\frac 12$ and $n=10^4$ gives $\color{red}{3.2931}33$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .