33
$\begingroup$

What would you suggest here?

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

$\endgroup$
  • $\begingroup$ looks a bit like a riemann sum for me $\endgroup$ – Dominic Michaelis Feb 18 '13 at 11:50
  • $\begingroup$ Seems to be really difficult, mathematica doesn't give me a result, you already know its converging ? $\endgroup$ – Dominic Michaelis Feb 18 '13 at 11:54
  • $\begingroup$ @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$. $\endgroup$ – user 1357113 Feb 18 '13 at 11:57
  • $\begingroup$ Is the question to prove convergence or to find the limit? $\endgroup$ – Ishan Banerjee Feb 18 '13 at 12:00
  • 2
    $\begingroup$ learn more approaching ways, do you mean you have one solution already? $\endgroup$ – user45099 Feb 18 '13 at 12:02
29
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ The answers posted in those websites are hard to follow. Please see the following two solutions since they are much simpler. $\endgroup$ – xpaul Apr 18 '13 at 4:10
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Aryabhata Apr 17 '13 at 7:44
  • $\begingroup$ @xpaul Thank you. Well, if you can make things easier I have nothing against. (+1) $\endgroup$ – user 1357113 Apr 17 '13 at 8:22
  • $\begingroup$ @Aryabhata, I will use your suggestion to modify. Thanks. $\endgroup$ – xpaul Apr 17 '13 at 12:16
  • $\begingroup$ @Sasha, please look at the new proof. $\endgroup$ – xpaul Apr 19 '13 at 0:47
  • $\begingroup$ Bernoulli's inequality also works: $$(n+1)^{1/k} - n^{1/k}=n^{1/k}\left(\left(1+\frac{1}{n}\right)^{1/k}-1\right) <n^{1/k}\left(1+\frac{1}{n}\frac{1}{k}-1\right)=\frac{1}{kn^{1-1/k}} \le \frac{1}{k\sqrt{n}}.$$ $\endgroup$ – Riemann Oct 16 '18 at 2:59
6
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Interesting approach (+1) $\endgroup$ – user 1357113 Jul 26 '13 at 11:41
3
$\begingroup$

I tried to post this answer to the question How to solve $\lim_{n \to \infty} \frac{n+n^{\frac{1}{2}}+n^{\frac{1}{3}}+...+n^{\frac{1}{n}}}{n}$. Then I noticed that it was a duplicate of the present one. Having seen that my solution method did not yet appear here I add it.

Answer

The limit in question is 2.

The graph depicts the partial sums for $n= 1..500$.

enter image description here

Notice that there is a maxiumum at $n=13$ and that the limit $s(\infty)=2$ is approached from above and very slowly.

Derivation

We have to calculate the limit of this sum

$$s_{n} = \sum_{k=1}^n c_{k}\tag{1a}$$

Where

$$c_{k} = c(k) = n^{\frac{1}{k}-1}\tag{1b}$$

We use partial summation in the integral form (see my answer to Does $\sum_{n=1}^\infty \frac{\cos{(\sqrt{n})}}{n}$ converge?) which gives us

$$s_{n} = i_0 + i_1(n) - i_2(n)\tag{2a}$$

Where $$i_0 = c_1 = 1\tag{2b}$$ $$i_1(n) = \int_{1}^n c(x)\,dx\tag{2c}$$ $$i_2(n) = - \int_{1}^n \{x\} c'(x)\,dx\tag{2d}$$

where $\{x\}$ is the fractional part of $x$.

The first integral can be done (Mathematica) leading to

$$i_1(n) = -\frac{\log (n) \text{Ei}\left(\frac{\log (n)}{n}\right)}{n}+\frac{\log (n) \text{Ei}(\log (n))}{n}+n^{1/n}-1\tag{3a}$$

Where $\text{Ei}$ is the exponential integral function.

In the limit we find

$$i_1(\infty) = \lim_{n\to \infty } \, i_1(n) = 1\tag{3b}$$

The second integral will be shown to vanish in the limit, so that we find the announced answer

$$s_{\infty} = i_0 + i_1(\infty) = 2\tag{4}$$

Indeed, since

$$c'(x) = -\left(\frac{\log (n)}{n}\right)\left(\frac{n^{\frac{1}{x}}}{x^2}\right)\tag{1c}$$

the second integral, after transforming $x\to\frac{1}{y}$, becomes

$$i_2(n) = \frac{\log (n)}{n}\int_{\frac{1}{n}}^1 \{\frac{1}{y}\} n^{y} \,dy \tag{5}$$

Observing that

$$0 \lt \{\frac{1}{y}\} \le \left(\frac{1}{y}-1 \right)\text{ for} \;\;0 \lt y \lt 1 \tag{6}$$

we have

$$i_{2}(n) \le \frac{\log (n)}{n}\int_{\frac{1}{n}}^1 \left(\frac{1}{y} -1\right) n^{y} \,dy \\ = \left(\frac{\log (n)}{n}\right) \left(\text{Ei}\left(\frac{\log (n)}{n}\right)+\text{Ei}(\log (n))+\frac{n^{1/n}-n}{\log (n)}\right)\tag{7}$$

The asymptotic behaviour of this expression is

$$\frac{1}{\log (n)}+O\left(\frac{\log ^2(n)}{n}\right)\tag{8}$$

This goes to zero, albeit very slowly.

Hence we have obtained the inequality

$$0 \lt i_2(n) \lt \frac{1}{\log (n)}+O\left(\frac{\log ^2(n)}{n}\right)$$

Which means that in the limit $i_{2}(\infty)=0$.

EDIT 19.10.18

Simplification of limit of the integral $i_1$.

We have

$$i_1(n) = \int_{1}^n c(x)\,dx= \frac{1}{n}\int_{1}^n n^{\frac{1}{x}}\,dx= \frac{1}{n}\int_{\frac{1}{n}}^1 n^{y}\frac{1}{y^2}\,dy$$

Since the main contribution comes from $y\simeq 0$ we can expand $n^y$ into a power series and write

$$i_1(n) = \frac{1}{n}\int_{\frac{1}{n}}^1 \left(1+y \log(n) + \frac{1}{2}y^2 \log(n)^2+...\right)\frac{1}{y^2}\,dy\\ =\frac{1}{n}\left(\left( n-1\right)-\left(\log \left(\frac{1}{n}\right) \log (n)\right)+ \left(\frac{1}{2} \left(1-\frac{1}{n}\right) \log ^2(n)\right)+... \right)$$

Hence we find for the limit

$$i_1(\infty) = \lim_{n\to \infty } \,i_1(n)=1$$

Unfortunately, things are not as easy for $i_2$, so that we have to stick to the formula (7) etc.

$\endgroup$

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.