What is the asymptotic behavior of the sequence: \begin{equation} s_n=\sum_{k=1}^{n}k^{1/4} \end{equation} when $n\to \infty$?

  • 9
    $\begingroup$ Are you familiar with Riemann sums? These yield immediately the equivalent $\frac45n^{5/4}$ (and even, much more precise inequalities). $\endgroup$ – Did Jan 31 '12 at 11:41
  • 2
    $\begingroup$ Thank you. I've read the wikipedia link and now I think you mean something like this: looking at the interval $[0,n]$, subdivide it in $n$ subintervals. Then, $\sum^{n-1}k^{1/4}<\int_0^n x^{1/4} dx<\sum^n k^{1/4}$. The integral is just what you write. Is this correct? Can it be made more formal? And how can you get even more precise inequalities? Thanks again $\endgroup$ – quark1245 Jan 31 '12 at 11:56
  • $\begingroup$ Pretty much. See answer. $\endgroup$ – Did Jan 31 '12 at 12:40

Let $k\geqslant1$. Since the function $x\mapsto x^{1/4}$ is increasing, $(k-1)^{1/4}\leqslant x^{1/4}\leqslant k^{1/4}$ for every $k-1\leqslant x\leqslant k$. Integrating this double inequality yields $$ (k-1)^{1/4}\leqslant\int_{k-1}^kx^{1/4}\mathrm dx\leqslant k^{1/4}. $$ Summing these from $k=1$ to $k=n$ yields $$ s_{n-1}=\sum_{k=0}^{n-1}k^{1/4}\leqslant\int_{0}^nx^{1/4}\mathrm dx\leqslant \sum_{k=1}^{n}k^{1/4}=s_n. $$ Since the integral is $\tfrac45n^{5/4}$ and $s_{n-1}=s_n-n^{1/4}$, this yields, for every $n\geqslant1$, $$ \tfrac45n^{5/4}\leqslant s_n\leqslant\tfrac45n^{5/4}+n^{1/4}. $$ Note finally that $n^{1/4}=o(n^{5/4})$ hence a (much weakened) version of this is $s_n\sim\tfrac45n^{5/4}$.


Here is a diagram to accompany Did's fine answer:

enter image description here

  • $\begingroup$ How was the diagram made? $\endgroup$ – lhf Feb 14 '12 at 16:11
  • $\begingroup$ @lhf Using JSXGraph. $\endgroup$ – David Mitra Feb 14 '12 at 16:18

There is a standard technique that produces the complete asymptotic expansion for this sum and many others like it, which is to use harmonic sums and Mellin transforms.

Introduce the telescoping sum $$S(x) = \sum_{k\ge 1} \left(\sqrt[4]{k}-\sqrt[4]{x+k}\right).$$ This sum has the property that $$S(n) = \sum_{q=1}^n \sqrt[4]{q},$$ so that $S(n)$ is the value we are looking for.

Re-write the sum as follows: $$S(x) = \sum_{k\ge 1} \sqrt[4]{k} \left(1-\sqrt[4]{x/k+1}\right).$$

The sum term is harmonic and may be evaluated by inverting its Mellin transform.

Recall the harmonic sum identity $$\mathfrak{M}\left(\sum_{k\ge 1} \lambda_k g(\mu_k x);s\right) = \left(\sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} \right) g^*(s)$$ where $g^*(s)$ is the Mellin transform of $g(x).$

In the present case we have $$\lambda_k = \sqrt[4]{k}, \quad \mu_k = \frac{1}{k} \quad \text{and} \quad g(x) = 1 - \sqrt[4]{1+x}.$$

It follows that $$\sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} = \sum_{k\ge 1} \sqrt[4]{k}\times k^s = \zeta(-1/4-s)$$ which has fundamental strip $-1/4-s > 1$ or $s < -5/4.$

We need the Mellin transform $g^*(s)$ of $g(x)$ which is $$\int_0^\infty \left(1 - \sqrt[4]{1+x}\right) x^{s-1} dx$$ which is immediately seen to be a beta function integral with value $$g^*(s) = - \frac{1}{\Gamma(-1/4)} \Gamma(s)\Gamma(-1/4-s)$$ and fundamental strip $\langle -1, -1/4 \rangle,$ which is a problem, because the abscissa of convergence of the zeta function term lies outside this strip. Hence we need to shift $g^*(s)$ by using $$ g(x) = 1 + \frac{1}{4} x - \sqrt[4]{1+x}$$ with fundamental strip $\langle -2, -1 \rangle,$ which is good.

We have now added the following quantity to our sum: $$\sum_{k\ge 1} \sqrt[4]{k} \frac{1}{4} \frac{x}{k} = \frac{1}{4} x \zeta(3/4),$$ which we will have to remember to subtract from our final answer.

It follows that the Mellin transform $Q(s)$ of the harmonic sum $S(x)$ is given by $$Q(s) = - \frac{1}{\Gamma(-1/4)} \Gamma(s)\Gamma(-1/4-s) \zeta(-1/4-s).$$ The Mellin inversion integral here is $$\frac{1}{2\pi i} \int_{-3/2-i\infty}^{-3/2+i\infty} Q(s)/x^s ds$$ which we evaluate by shifting it to the right for an expansion at infinity.

First treat the pole from the zeta function term at $s=-5/4$, which has $$\mathrm{Res}(Q(s)/x^s; s=-5/4) = -\frac{1}{\Gamma(-1/4)} \Gamma(-5/4)\Gamma(1)\times -1 \times x^{5/4} = -\frac{4}{5} x^{5/4}.$$ For the pole at $s=-1$ we get $$\mathrm{Res}(Q(s)/x^s; s=-1) = -\frac{1}{4}\zeta(3/4)x.$$ We see that this is precisely the contribution that we added in when we shifted $g^*(s)$ into position and hence this residue will not be included in the asymptotic expansion.

For the pole at $s=-1/4$ from the compound gamma function term we obtain $$\mathrm{Res}(Q(s)/x^s; s=-1/4) = -\frac{1}{\Gamma(-1/4)} \Gamma(-1/4) \times -1 \times\zeta(0) = -\frac{1}{2} \sqrt[4]{x}.$$ For the pole at $s=0$ from the simple gamma function term we obtain $$\mathrm{Res}(Q(s)/x^s; s=0) = -\frac{1}{\Gamma(-1/4)} \Gamma(-1/4) \zeta(-1/4) = -\zeta(-1/4).$$

The remaining poles are at $s = q-1/4$ where $q\ge 1$ and contribute $$\mathrm{Res}(Q(s)/x^s; s=q-1/4) = -\frac{1}{\Gamma(-1/4)} \Gamma(q-1/4) \frac{(-1)^{q+1}}{q!} \zeta(-q) \frac{1}{x^{q-1/4}} \\ = - \prod_{p=0}^{q-1} (p-1/4) \times \frac{(-1)^{q+1}}{q!} (-1)^q \frac{B_{q+1}}{q+1} \frac{1}{x^{q-1/4}} = \frac{1}{4^q} B_{q+1} \frac{\prod_{p=0}^{q-1} (4p-1)}{(q+1)!} \frac{1}{x^{q-1/4}}.$$ The zero values of the Bernoulli numbers correctly represent cancelation of the gamma function poles by the trivial zeros of the zeta function.

Setting $x=n$ and observing that the shift to the right produces a minus sign we obtain the following asymptotic expansion: $$S(n) = \sum_{k=1}^n \sqrt[4]{k} \sim \frac{4}{5} n^{5/4} + \frac{1}{2} \sqrt[4]{n} + \zeta(-1/4) - \sum_{q\ge 1} \frac{1}{4^q} B_{q+1} \frac{\prod_{p=0}^{q-1} (4p-1)}{(q+1)!} \frac{1}{n^{q-1/4}}.$$

Actually computing the Bernoulli number terms we get the expansion $$\frac{4}{5} n^{5/4} + \frac{1}{2} \sqrt[4]{n} + \zeta(-1/4) + 1/48\,{n}^{-3/4}-{\frac {7}{15360}}\,{n}^{-11/4}+{\frac {11}{98304}}\, {n}^{-{\frac {19}{4}}}\\-{\frac {4807}{62914560}}\,{n}^{-{\frac {27}{4}} }+{\frac {13547}{134217728}}\,{n}^{-{\frac {35}{4}}}-{\frac {9360977}{ 42949672960}}\,{n}^{-{\frac {43}{4}}}\\+{\frac {191649409}{274877906944} }\,{n}^{-{\frac {51}{4}}}-{\frac {1089307862269}{351843720888320}}\,{n }^{-{\frac {59}{4}}} +\cdots.$$

This MSE link points to a series of similar calculations.

Care must be taken with the asymptotics of these expansions since the Bernoulli numbers eventually outgrow all other terms. For example when $n=10$ the sum of the first $62$ Bernoulli terms converge to produce thirty digits of precision and diverge from then on. These expansions fit the definition however, where we say that an asymptotic sequence $\{\phi_k(n)\}$ has $$|\phi_{k+1}(n)/\phi_k(n)|\rightarrow 0$$ as $n\rightarrow\infty$ and $$\lim_{n\rightarrow\infty}\frac{|S(n)-\sum_{k=1}^m\phi_k(n)|}{\phi_m(n)}=0.$$

  • $\begingroup$ I recommend looking into Euler-Maclaurin summation, which provides a general technique to find such asymptotic expansions. $\endgroup$ – Eric Naslund Mar 25 '15 at 2:54
  • $\begingroup$ I agree that Euler-MacLaurin is more general, what I meant was to present the trick with the telescoping sum which is also used at this MSE link. I believe it deserves being presented, I myself learned it from a Flajolet paper and I suppose it is somewhere in the Flajolet / Sedgewick book as well. I hope the above was a competent presentation. $\endgroup$ – Marko Riedel Mar 25 '15 at 3:07
  • $\begingroup$ The precise reference for the telescoping sum is page 40 "Chapter 7 Mellin Transform Asymptotics" by Flajolet / Sedgewick, INRIA Rapport de recherche 2956 (1996). $\endgroup$ – Marko Riedel Mar 25 '15 at 3:48
  • $\begingroup$ This sum also appears as example B.28 on page 766 of the internet edition of the Flajolet / Sedgewick book. $\endgroup$ – Marko Riedel Mar 25 '15 at 4:05
  • $\begingroup$ I've been looking at Flajolet and some of your expositions; I cannot quite find a firm statement on this: (Apparently) For real $0 < \sigma < 1,$ we have $$ \zeta(\sigma) \; \; = \; \; \lim_{n \rightarrow \infty} \; \; \left( \sum_{k=1}^n \frac{1}{k^\sigma} \right) - \frac{n^{1-\sigma}}{1-\sigma} $$ example $$ \lim_{n \rightarrow \infty} \; \; \left( \sum_{k=1}^n \frac{1}{\sqrt[3] k} \right) - \frac{3 n^{2/3}}{2} - \frac{1}{2 \sqrt[3] n} + \frac{1}{36 n^{4/3}} \; \; = \; \; \zeta \left(\frac{1}{3}\right) \approx -0.973360248350782 $$ $\endgroup$ – Will Jagy Jan 7 '18 at 17:07

Euler McLaurin Summation yields:

$$\sum_{k=0}^{n} k^{1/4} = \frac{4}{5} n^{5/4} + \frac{1}{2} n^{1/4} + C + \mathcal{O}(n^{-3/4})$$

It can be shown that $C = \zeta(-1/4)$ where $\zeta$ is the Riemann-Zeta function as defined on the whole plane.

Note that this is a much stronger statement than $\sum_{k=0}^{n}k^{1/4} \sim \frac{4}{5} n^{5/4}$, which (in the current context) means that

$$\lim_{n \to \infty} \frac{\sum_{k=0}^{n}k^{1/4}}{\frac{4}{5} n^{5/4}} = 1$$

What Euler Mclaurin gives us is the following:

$$\lim_{n \to \infty} \sum_{k=0}^{n}k^{1/4}- \frac{4}{5} n^{5/4} - \frac{1}{2} n^{1/4} - C = 0 $$

Which actually implies that

$$\lim_{n \to \infty} \sum_{k=0}^{n}k^{1/4}- \frac{4}{5} n^{5/4} = \infty$$ There is also an elementary proof of this fact (but which does not determine the exact value of $C$) here: How closely can we estimate $\sum_{i=0}^n \sqrt{i}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.