2
$\begingroup$

The asymptotics of the sum $\displaystyle S_n=\sum_{k=1}^nn^{1/k}$ can be found, for example, by means of Stolz-Césaro theorem (for example, here); I found it via the Euler-Maclaurin' summation formula.

The answer is $$S_n=n+n^{1/2}+n^{1/3}+n^{1/4}+...+n^{1/n}\sim 2n+n^{1/2}+n^{1/3}+n^{1/4}+...$$ As we deal with the asymptotic series, we may expect that there is no contradiction here.

So, my questions are:

  1. How many term of the asymptotics (depending on $n$) we are allowed to retain?
  2. How we can evaluate (or estimate) the remainder term?

Thank you.

$\endgroup$
6
  • 2
    $\begingroup$ I don't understand. This is almost like saying $S_n$ is asymptotic to itself. This statement is equivalent to saying that $n/S_n$ vanishes as $n\to\infty$ which is not exactly a sharp asymptotic equivalence, it is just an estimate $S_n\in\omega(n)$. Surely, you would want a better estimate in terms of something more tangible; Stirling's formula is useful, but $n!\sim n!+n$ is not. $\endgroup$
    – FShrike
    Oct 12, 2023 at 12:30
  • 1
    $\begingroup$ @FShrike, I agree, it looks like a paradox. I guess the point is that in the sum we sum up all $n$ terms, but in the asymptotics we are allowed to keep less than $n$ terms. You may also evaluate $\lim_{n\to\infty}\frac1{\sqrt n}(S_n-2n)=1$ $\endgroup$
    – Svyatoslav
    Oct 12, 2023 at 12:47
  • $\begingroup$ I'm just not sure what the question is. About the "allowed to retain" etc. As written this seems like a useless asymptotic estimate for $S_n$ $\endgroup$
    – FShrike
    Oct 12, 2023 at 12:57
  • $\begingroup$ You can get $n^{-1/k}((S_n-n)-(n+n^{1/2}+\dots+n^{1/(k-1)}))\to 1$ for all $k\geq 2$ with similar methods. I don't know what your point is, because the extra $n$ comes from all remaining $n^{1/(k+1)},n^{1/(k+2)},\dots, n^{1/n}$ as $\geq 1$ and an estimate of their upper bound. $\endgroup$ Oct 12, 2023 at 13:37
  • $\begingroup$ @FShrike, I would like to find $k(n)$, so that $$S_n=n+\sum_{i=1}^{k(n)}n^{1/i}+R(n)$$, where the remainder $R(n)=o\big(n^{1/k}\big)$ and, if possible, to get an explicite form of $R(n)$ $\endgroup$
    – Svyatoslav
    Oct 12, 2023 at 13:42

2 Answers 2

2
$\begingroup$

Let $N$ be some positive integer to be determined later, so we have

$$ S_n=\sum_{k=1}^Nn^{1/k}+\sum_{k=N+1}^nn^{1/k}. $$

Notice that when $k>\log n$, we have $n^{1/k}=1+{\log n\over k}+O\left(\log^2n\over k^2\right)$. This indicates that when $N=\lfloor\log n\rfloor$, there is

$$ \begin{aligned} \sum_{k=N+1}^nn^{1/k} &=\sum_{k=N+1}^n1+\sum_{k=N+1}^n{\log n\over k}+O\left(\sum_{k=N+1}^n{\log^2n\over k^2}\right) \\ &=n-N+(\log n)\log{n\over N+1}+O\left(\log n\over N\right)+O\left(\log^2n\over N\right) \\ &=n+O(\log^2n). \end{aligned} $$

Consequently, we have the following asymptotic expansion:

$$ S_n=2n+n^{1/2}+n^{1/3}+\dots+n^{1/\lfloor\log n\rfloor}+O(\log^2n). $$

$\endgroup$
4
  • 2
    $\begingroup$ (+1) In $O\left(\sum_{k=N+1}^n{\log^2n\over k}\right)$ you should divide by $k^2$. $\endgroup$
    – Gary
    Oct 14, 2023 at 1:12
  • $\begingroup$ Thank you for your solution! I got the similar result (the remainder $O(\ln^2n)$), but in a more complicated way. I think your solution is the shortcut to the answer. Interestingly, we are allowed to retain a very slow growing number ($[\ln n]$) of terms in the asymptotics. $\endgroup$
    – Svyatoslav
    Oct 14, 2023 at 5:48
  • $\begingroup$ @Gary Just edited. Thanks for pointing that out $\endgroup$
    – TravorLZH
    Oct 14, 2023 at 14:22
  • 2
    $\begingroup$ @Svyatoslav If you are happy to take more terms then you can gain a better error term: $$ \sum\limits_{k = 1}^n {n^{1/k} } = 2n + \bigg( {\sum\limits_{k = 2}^{\left\lfloor {\log ^2 (n)} \right\rfloor } {n^{1/k} } } \bigg) - 2\log (n)\log \log (n) + \mathcal{O}(1). $$ $\endgroup$
    – Gary
    Oct 16, 2023 at 4:12
1
$\begingroup$

You add $n$ terms each $\ge 1$, that’s $n$ in total. The first term is $n$, the second $\sqrt n$, the third $n^{1/3}$, I bet the sum is $2n + \sqrt n + O{(n^{1/3})}$.

$\endgroup$

You must log in to answer this question.

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