# The limit of $\frac{n+\sqrt{n}+\cdots+\sqrt[n]{n}}{n}$

How do I compute the following limit or show it doesn't exists? $$\lim_{n\rightarrow\infty}\frac{n+\sqrt{n}+\cdots+\sqrt[n]{n}}{n}$$

I've struggled with this problem for a while now so I would appreciate a complete solution.

-
In your struggle, what have you come up with, and what did you try to use? – user23211 Jun 27 '12 at 0:48
@ymar Intuitively, the first few terms are significant because they are large and the last bunch of terms contribute because there are many of them. I have tried to split up the sum accordingly to no avail. – ryan Jun 27 '12 at 0:56
@ryan: how have you tried splitting the sum? (Have you tried splitting into the first $r$ terms and the rest without specifying $r$ in advance?) – Qiaochu Yuan Jun 27 '12 at 1:02
Stolz-Cesáro theorem is the way to go in such cases. It works fast and nice. – I'm an artist Jun 27 '12 at 4:51

The limit is $2$.

Indeed by the Stolz-Cesáro theorem it suffices to show

$$\lim_{n\rightarrow\infty}\frac{\sum_{k=1}^{n+1}(n+1)^{1/k}-\sum_{k=1}^{n}n^{1/k}}{(n+1)-n}=\lim_{n\rightarrow\infty}1+(n+1)^{1/(n+1)}+\sum_{k=2}^{n}\left \{(n+1)^{1/k}-n^{1/k}\right \}=2.$$

Thus we need only show

$$\lim_{n\rightarrow\infty}\sum_{k=2}^{n}(n+1)^{1/k}-n^{1/k}=0.$$

The concavity of $x\mapsto x^{1/k}$ implies $(n+1)^{1/k}-n^{1/k}\leq n^{1/k-1}/k.$

Hence

\begin{align*} \sum_{k=2}^{n}(n+1)^{1/k}-n^{1/k}&\leq\sum_{k=2}^n\frac{n^{1/k-1}}{k}\\ &\leq\frac{1}{\sqrt n}\sum_{k=2}^n\frac{1}{k}=\mathcal{O}\left (\frac{\log n}{\sqrt n}\right ). \end{align*}

Since the relevant sum is manifestly positive for each $n$, it follows that $\lim_{n\rightarrow\infty}\sum_{k=2}^{n}(n+1)^{1/k}-n^{1/k}=0.$

-

Well, since there is already an answer, let me link to this blog post where I describe how to compute this limit (and estimate the rate of convergence) by splitting the sum.

-

The first term of the sum contributes $1$, so the focus would be on determining the limit of the average of the sum of the remaining terms. Since $n^{1 \over k}$ is approximately $1$ for the vast majority of these terms, it makes sense that this average will converge to $1$. Formally:

Given $\epsilon > 0$, we have that $1 < n^{1 \over k} < 1 + \epsilon$ whenever $k > k_0 = \frac{\ln(n)}{\ln(1 + \epsilon)}$. Thus we have $$\frac{n - k_0 - 1}{n} < {\sum_{k > k_0}n^{1 \over k} \over n} < (1 + \epsilon)\frac{n - k_0}{n}$$ On the other hand, for $2 \leq k \leq k_0$ the first term is largest, so we can bound each term by the first and we get $${\sum_{2 \leq k \leq k_0}n^{1 \over k} \over n} < \frac{k_0}{\sqrt{n}}$$ Adding these together and plugging back in for $k_0$ we get $$\frac{n -\frac{\ln(n)}{\ln(1 + \epsilon)}-1}{n} < {\sum_{k \geq 2}n^{1 \over k} \over n} < (1 + \epsilon)\frac{n -\frac{\ln(n)}{\ln(1 + \epsilon)}}{n} + \frac{\ln(n)}{\sqrt{n}\ln(1 + \epsilon)}$$ The right-hand side of this leads to $$\limsup_{n \rightarrow \infty} {\sum_{k \geq 2}n^{1 \over k} \over n} \leq 1 + \epsilon$$ The left-hand side leads to $$\liminf_{n \rightarrow \infty} {\sum_{k \geq 2}n^{1 \over k} \over n} \geq 1$$ These hold for any $\epsilon > 0$, so the overall limit is $1$. Adding this to the $k=1$ term, we see the original limit is $2$.

-