# Methods to find $\lim\limits_{n\to\infty} \frac{1}{n} \sum_{k=1}^{n} n^{1/k}$

What would you suggest here?

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

-
looks a bit like a riemann sum for me – Dominic Michaelis Feb 18 '13 at 11:50
Seems to be really difficult, mathematica doesn't give me a result, you already know its converging ? – Dominic Michaelis Feb 18 '13 at 11:54
@DominicMichaelis: if you take $n$ finite, like $n=10^6$, W|A gives an answer that is $\approx 2$. I think the limit should be $2$. – user 1618033 Feb 18 '13 at 11:57
Is the question to prove convergence or to find the limit? – Ishan Banerjee Feb 18 '13 at 12:00
learn more approaching ways, do you mean you have one solution already? – user45099 Feb 18 '13 at 12:02

AM $\ge$ GM seems sufficient to give a simple and elementary approach.

For $k \ge 2$, we have, taking $k-2$ copies of $1$ and two copies of $\sqrt{n}$, that

$$\frac{1 + 1 + \dots + 1 + \sqrt{n} + \sqrt{n}}{k} \ge n^{1/k} \ge 1$$

i.e.

$$1 - \frac{2}{k} + \frac{2 \sqrt{n}}{k} \ge n^{1/k} \ge 1$$

Thus

$$(n-1) + 2(H_n - 1)(\sqrt{n} - 1) \ge \sum_{k=2}^{n} n^{1/k} \ge n-1$$

And so

$$2n-1 + 2(H_n - 1)(\sqrt{n} - 1) \ge \sum_{k=1}^{n} n^{1/k} \ge 2n-1$$ Where $H_n$ is the $n^{th}$ harmonic number.

Divide by $n$, and by the squeeze theorem, we have that

$$\lim_{n \to \infty} \frac{1}{n}\sum_{k=1}^{n} n^{1/k} = 2$$

This AM $\ge$ GM idea was also used in the answer here: Proof that $\lim_{n\rightarrow \infty} \sqrt[n]{n}=1$ and a slight variant here: How to prove $\lim_{n \to \infty} \sqrt{n}(\sqrt[n]{n} - 1) = 0$? and

-
This solution looks amazing. Such an answer I expected. Very very nice. – user 1618033 Apr 17 '13 at 8:06
I love this answer so much! :-) – user 1618033 Apr 17 '13 at 8:25
It is a nice solution. I like it. – xpaul Apr 17 '13 at 12:25
@Chris'ssisterandpals/@xpaul: Glad you liked it :-) – Aryabhata Apr 18 '13 at 0:25

HINT: Looking at the sum, there are two major sources of contribution - the first few terms are large, but there are also lots of small terms on the tail that add up. So we must bound them separately, as any bounding of all terms at once will be too coarse. So separate the first $m$ terms from the rest, and estimate each part. Then look back at how to choose the $m$ so as to obtain a decent bound.

If you need more details than the hint, this page goes through the details of the method I proposed, while this takes a different approach entirely.

-
Thanks for your answer! – user 1618033 Mar 1 '13 at 14:00
The answers posted in those websites are hard to follow. Please see the following two solutions since they are much simpler. – xpaul Apr 18 '13 at 4:10

I made a mistake before. Now I want to fix it. I looked at the link posted above and the solution is very long and hard to follow. Please look at the solution below to see if it is correct. Note that $$\frac{1}{n}\sum_{k=1}^nn^{1/k}=1+\frac{1}{n}\sum_{k=2}^{n}n^{1/k}.$$ Now we will show that \begin{eqnarray} \tag{1} \lim_{n\to\infty}\frac{1}{n}\sum_{k=2}^{n}n^{1/k}=1. \end{eqnarray} Let $a_n=\sum_{k=2}^{n}n^{1/k}$ and $b_n=n$. By the Stolz-Cesaro theorem, \begin{eqnarray*} \lim_{n\to\infty}\frac{1}{n}\sum_{k=2}^{n}n^{1/k}&=&\lim_{n\to\infty}\frac{a_n}{b_n}\\ &=&\lim_{n\to\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}\\ &=&\lim_{n\to\infty}(a_{n+1}-a_n)\\ &=&\lim_{n\to\infty}\sum_{k=2}^{n+1}(n+1)^{1/k}-\sum_{k=2}^{n}n^{1/k}\\ &=&\lim_{n\to\infty}\left(\sum_{k=2}^{n}\left[(n+1)^{1/k}-n^{1/k}\right]+(n+1)^{1/(n+1)}\right)\\ &=&\lim_{n\to\infty}\sum_{k=2}^{n}\left[(n+1)^{1/k}-n^{1/k}\right]+1. \end{eqnarray*} Note that by the Mean Value theorem, it is easy to check $$(n+1)^{1/k}-n^{1/k}\le \frac{1}{kn^\frac{k-1}{k}}\le\frac{1}{kn^{1/2}}$$ and hence \begin{eqnarray*} 0<\sum_{k=2}^{n}\left[(n+1)^{1/k}-n^{1/k}\right]\le\sum_{k=2}^{n}\frac{1}{kn^{1/2}}=\frac{1}{n^{1/2}}\sum_{k=2}^n\frac{1}{k}=\frac{1}{n^{1/2}}(\ln n-1+\gamma+o(1))\to 0 \end{eqnarray*} as $n\to\infty$. So (1) is true. Thus $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^nn^{1/k}=2.$$ Thank you, Aryabhata, for the suggestion to simplify the solution

-
The approach looks right: you can use the Mean Value theorem to show that $$(n+1)^{1/k} - n^{1/k} \le \frac{1}{kn^{1-1/k}} \le \frac{1}{k\sqrt{n}}$$ to simplify your proof considerably. Your attempts to prove the fact I just stated are a bit hard to understand. I suggest you replace it with something simpler. +1, though. – Aryabhata Apr 17 '13 at 7:44
@xpaul Thank you. Well, if you can make things easier I have nothing against. (+1) – user 1618033 Apr 17 '13 at 8:22
@Aryabhata, I will use your suggestion to modify. Thanks. – xpaul Apr 17 '13 at 12:16
@Sasha, please look at the new proof. – xpaul Apr 19 '13 at 0:47

Using Bernoulli's Inequality, we get for $k\ge\log(n)$ $$\frac1n\ge\left(1-\frac{\log(n)}{k}\right)^k\tag{1}$$ from which it is simple to derive $$n^{1/k}-1\le\frac{\log(n)}{k-\log(n)}\tag{2}$$ Just multiplying the number of terms by the largest term, we get \begin{align} \sum_{k=2}^{\lfloor\log(n)\rfloor+1}\left(n^{1/k}-1\right) &\le(\sqrt{n}-1)\lfloor\log(n)\rfloor\\ &\le\sqrt{n}\,\log(n)\tag{3} \end{align} Using $(2)$, we get \begin{align} \sum_{k=\lfloor\log(n)\rfloor+2}^n\left(n^{1/k}-1\right) &\le\sum_{k=\lfloor\log(n)\rfloor+2}^n\frac{\log(n)}{k-\log(n)}\\ &\le\log(n)(\log(n)+\gamma)\\[8pt] &\le(\log(n)+\gamma)^2\tag{4} \end{align} Combine $(3)$ and $(4)$ to get $$\lim_{n\to\infty}\frac1n\sum_{k=2}^n\left(n^{1/k}-1\right)=0\tag{5}$$ Therefore, $$\lim_{n\to\infty}\frac1n\sum_{k=1}^nn^{1/k}=2\tag{6}$$

-
Interesting approach (+1) – user 1618033 Jul 26 '13 at 11:41