# Proof verification for $\lim_{n\to\infty}\frac{1}{n}(1+\sqrt2+\dots + \sqrt{n}) = +\infty$

Show that: $$\lim_{n\to\infty}\frac{1}{n}(1+\sqrt2+\dots + \sqrt{n}) = +\infty$$

I've tried the following way. Consider the following sum: $$\sqrt n + \sqrt{n-1} + \dots + \sqrt{n-\frac{n}{2}} + \dots + \sqrt{2} + 1$$

Now if we take only $$n\over 2$$ terms of the sum we obtain that: $$\sqrt n + \sqrt{n-1} + \dots > {n \over 2} \sqrt{n\over 2}$$ Let: $$x_n = {1 \over n}(1 + \sqrt{2} + \dots + \sqrt{n}),\ \ n\in \Bbb N$$

Using the above we have that: $$x_n > {1\over n} {n\over 2}\sqrt{n\over 2} = {1\over 2} \sqrt{n \over 2}$$ Now taking the limit for RHS its obvious that: $$\lim_{n\to\infty}{1\over2}\sqrt{n\over2} = +\infty$$ Which implies: $$\lim_{n\to \infty}x_n = + \infty$$

Have I done it the right way? Also i would appreciate alternative ways of showing that limit. Thanks!

• It's a very good way to do it! – zhw. Dec 8 '18 at 20:25

That's seems fine, the more straightforward alternative way is by Stolz-Cesaro, that is

$$\frac{1+\sqrt2+\dots + \sqrt{n+1}-(1+\sqrt2+\dots + \sqrt{n})}{n+1-n}=\sqrt{n+1}$$

As another one alternative, we can use AM-GM

$$\frac{1}{n}(1+\sqrt2+\dots + \sqrt{n}) \ge \sqrt[2n]{n!}$$

• @roman ok I try to add also another way! – user Dec 8 '18 at 19:26
• @roman We can also avoid Stirling using "Ratio-Root criterion", discussed HERE if you are interested. – user Dec 8 '18 at 19:41
• I don't consider S-C more straightforward. – zhw. Dec 8 '18 at 22:48
• I think the way the OP aproached it is the most straightforward. – zhw. Dec 9 '18 at 16:41
• It read to me like you were saying "I have an alternative approach that is more straightforward" – zhw. Dec 9 '18 at 16:50

$$\bigl(1+\sqrt2+\dots + \sqrt{n}\bigr)$$ is an upper Riemann sum, with the subdivision $$\{0,1,2,\dots ,n\}$$, for the integral $$\;\displaystyle \int_0^n\sqrt x\,\mathrm d x=\frac23n^{3/2}$$,so $$\frac1n\bigl(1+\sqrt2+\dots + \sqrt{n}\bigr)\ge\frac1n\int_0^n\sqrt x\,\mathrm d x=\frac23\sqrt n,$$ which tends to $$+\infty$$.

• Where does the $1/n$ come from in that integral? – Ned Dec 8 '18 at 19:42
• It's $\Delta x$. – Bernard Dec 8 '18 at 20:02
• isn't delta x equal to 1 for that subdivision? I think you can make the argument work on the interval [0,1] but the Riemann sum won't be the exact given expression. – Ned Dec 8 '18 at 20:07
• @Ned: Sorry, I completely messed up the argumentation. I've fixed that. Thanks for pointing the problem! – Bernard Dec 8 '18 at 20:22

In style to @Bernard's answer, but using this general (and very useful) trick $$\lim\limits_{n\rightarrow\infty} \frac{1}{n}\sum\limits_{k=1}^n f\left(\frac{k}{n}\right)= \int\limits_{0}^{1} f(x)dx$$ where $$f(x)=\sqrt{x}$$, we have $$\lim\limits_{n\rightarrow\infty} \frac{1}{n}\sum\limits_{k=1}^n \sqrt{\frac{k}{n}}= \int\limits_{0}^{1} \sqrt{x}dx=\frac{2}{3} \tag{1}$$ Now $$\frac{1}{n}\sum\limits_{k=1}^n \sqrt{k}=\sqrt{n}\left(\frac{1}{n}\sum\limits_{k=1}^n \sqrt{\frac{k}{n}}\right)\overset{(1)}{>}\sqrt{n}\left(\frac{2}{3}-\varepsilon \right) \tag{2}$$ from some $$n_0$$ onwards. And the result follows.

Just to give an alternative, note first that the sequence is increasing:

\begin{align} {1\over n+1}(1+\sqrt2+\cdots+\sqrt n+\sqrt{n+1})-{1\over n}(1+\sqrt2+\cdots\sqrt n) &={\sqrt{n+1}\over n+1}-{1+\sqrt2+\cdots+\sqrt n\over n(n+1)}\\ &\gt{\sqrt{n+1}\over n+1}-{n\sqrt n\over n(n+1)}\\ &={\sqrt{n+1}-\sqrt n\over n(n+1)} \end{align}

Now consider

\begin{align} {1\over n^2}(1+\sqrt2+\cdots+\sqrt{n^2}) &\gt{1\over n^2}(1+1+1+2+2+2+2+2+3+\cdots+(n-1)+n)\\ &={1\over n^2}(3\cdot1+5\cdot2+7\cdot3+\cdots+(2n-1)(n-1)+n)\\ &\gt{2\over n^2}(1^2+2^2+3^2+\cdots+(n-1)^2)\\ &={2\over n^2}\cdot{(n-1)n(2n-1)\over6}\\ &={(n-1)(2n-1)\over3n}\\ &\to\infty \end{align}

Just another way assuming that you already heard about generalized hormonic numbers.

$$\sum_{k=1}^n \sqrt k=H_n^{\left(-\frac{1}{2}\right)}$$ Now, the asymptotics $$H_n^{\left(-\frac{1}{2}\right)}=\frac{2 n^{3/2}}{3}+\frac{n^{1/2}}{2}+\zeta \left(-\frac{1}{2}\right)+\frac{1}{24n^{1/2}}+O\left(\frac{1}{n^{5/2}} \right)$$ So, for large values of $$n$$, $$\frac{\sum_{k=1}^n \sqrt k } n=\frac{2 n^{1/2}}{3}+\frac{1}{2n^{1/2}}+O\left(\frac{1}{n} \right)$$ which answers the question but also gives an approximation.

Fo raxample, using $$n=100$$, the exact calculation would give $$\approx 6.71463$$ while the above formula would give $$\frac{403}{60} \approx 6.71667$$ (relative error $$=0.03$$%).

The proof you've given is also the one I would have given (because it uses minimal resources), so I won't suggest an alternative - it just needs a little tweaking.

First, there's a minor typo: in two places, you've written $$\sqrt{n + 1}$$, where you meant $$\sqrt{n - 1}$$.

More seriously, you've assumed that $$n$$ is even: it doesn't make sense to talk of "$$\frac{n}{2}$$ terms" when $$n$$ is odd. This is easily remedied, because the idea of the proof is sound. One fix is as follows, although you may find a neater way:

Either $$n = 2k - 1$$ or $$n = 2k$$, where $$k$$ is a positive integer. The last $$k$$ terms of the sequence $$1, \sqrt{2}, \ldots, \sqrt{n}$$ are $$\sqrt{n - k + 1}, \sqrt{n - k + 2}, \ldots, \sqrt{n}$$. The smallest term is $$\sqrt{n - k + 1}$$, which is either $$\sqrt{k}$$ or $$\sqrt{k + 1}$$. Therefore, the sum of the $$k$$ terms is at at least $$k\sqrt{k}$$. Therefore it is at least $$\frac{n}{2}\sqrt{\frac{n}{2}}$$, because $$k \geqslant \frac{n}{2}$$.

Here's another simple idea, using only the very easily proved AM-GM inequality for two terms: $$\sum_{k=1}^n\sqrt{k} = \sum_{k=1}^n\frac{\sqrt{k} + \sqrt{n - k + 1}}{2} \geqslant \sum_{k=1}^n\sqrt{k(n - k + 1)} \geqslant n^{5/4},$$ because $$k(n - k + 1) - n = (k - 1)(n - k) \geqslant 0$$. Although very weak, it's enough for the job. (But I still prefer the solution given in the question.)

Looking for a proof using the Cauchy-Schwarz inequality, all I could come up with was this: $$\begin{gather*} \sqrt{k} - \sqrt{k - 1} = \frac{1}{\sqrt{k} + \sqrt{k - 1}} > \frac{1}{2\sqrt{k}} \quad (1 \leqslant k \leqslant n), \\ \therefore\ 1 + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} < 2\sqrt{n}; \\ \text{but } \left(1 + \sqrt{2} + \cdots + \sqrt{n}\right) \left(1 + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}}\right) \geqslant n^2, \text{ by C-S}; \\ \therefore\ 1 + \sqrt{2} + \cdots + \sqrt{n} > \frac{n\sqrt{n}}{2}. \end{gather*}$$

I came up with the following quite long but elementary argument as a way of avoiding the use of Jensen's inequality.

For all $$k \geqslant 1$$, we have

$$\sqrt{k + 1} - \sqrt{k} < \sqrt{k} - \sqrt{k - 1},$$

because $$\left(\sqrt{k + 1} + \sqrt{k - 1}\right)^2 = 2k + 2\sqrt{k^2 - 1} < 4k.$$

Lemma If $$n > 2$$, and $$a_2 - a_1 > a_3 - a_2 > \cdots > a_n - a_{n - 1} > 0$$, then $$\frac{a_1 + a_2 + \cdots + a_n}{n} > \frac{a_1 + a_n}{2}.$$

Proof Write $$b_k = a_{k+1} - a_k$$, so that $$(b_k)_{1 \leqslant k < n}$$ is a strictly decreasing sequence. For all $$k$$ such that $$1 < k < n$$, we have $$\begin{gather*} \frac{a_n - a_1}{a_k - a_1} = \frac{b_1 + b_2 + \cdots + b_{n-1}}{b_1 + b_2 + \cdots + b_{k-1}} = 1 + \frac{b_k + b_{k+1} + \cdots + b_{n-1}} {b_1 + b_2 + \cdots + b_{k-1}} \\ \leqslant 1 + \frac{(n - k)b_k}{(k - 1)b_{k-1}} < 1 + \frac{n - k}{k - 1} = \frac{n - 1}{k - 1}. \end{gather*}$$ Setting $$h = (a_n - a_1)/(n - 1)$$ and $$a_k' = a_1 + (k - 1)h$$, we therefore have $$a_1 = a_1'$$, $$a_n = a_n'$$, and $$a_k > a_k'$$ ($$1 < k < n$$), whence $$a_1 + a_2 + \cdots + a_n > a_1' + a_2' + \cdots + a_n' = n\frac{a_1' + a_n'}{2} = n\frac{a_1 + a_n}{2},$$ as required. $$\square$$

Taking $$a_k = \sqrt{k}$$ in the lemma, we get $$1 + \sqrt{2} + \cdots + \sqrt{n} > \frac{n\left(\sqrt{n} + 1\right)}{2} \quad (n > 2).$$

(Even after all this, I still prefer the OP's own proof - but looking for alternatives is fun.)

Here is another quite simple proof, which I think I prefer to the one given in the question. (Looking at the other answers, I see that it is a variant of a proof that Barry Cipra has already posted, but there are probably enough differences to make it still worth posting.)

If $$n \geqslant 4$$, there is a unique positive integer $$r$$ such that $$(r + 1)^2 \leqslant n < (r + 2)^2$$, and: \begin{align*} & \phantom{=} 1 + \sqrt{2} + \cdots + \sqrt{n} \\ & \geqslant 1 + (\sqrt{2} + \sqrt{3} + \sqrt{4}) + \cdots + (\sqrt{r^2 + 1} + \cdots + \sqrt{(r + 1)^2}) \\ & > 0 + (2^2 - 1^2) \cdot 1 + (3^2 - 2^2) \cdot 2 + \cdots + ((r + 1)^2 - r^2) \cdot r \\ & > 2 \cdot 1^2 + 2 \cdot 2^2 + \cdots + 2 \cdot r^2 \\ & = \frac{1}{3}r(r + 1)(2r + 1) > \frac{2}{3}r^3 \\ & > \frac{2}{3}\left(\sqrt{n} - 2\right)^3. \end{align*}

Although there's no need (for present purposes), one could also argue that for all $$n$$, there is a unique positive integer $$s$$ such that $$(s - 1)^2 < n \leqslant s^2$$, and: \begin{align*} & \phantom{=} 1 + \sqrt{2} + \cdots + \sqrt{n} \\ & \leqslant 1 + (\sqrt{2} + \sqrt{3} + \sqrt{4}) + \cdots + (\sqrt{(s - 1)^2 + 1} + \cdots + \sqrt{s^2}) \\ & \leqslant (1^2 - 0^2) \cdot 1 + (2^2 - 1^2) \cdot 2 + (3^2 - 2^2) \cdot 3 + \cdots + (s^2 - (s - 1)^2) \cdot s \\ & < 2 \cdot 1^2 + 2 \cdot 2^2 + 2 \cdot 3^2 + \cdots + 2 \cdot s^2 \\ & = \frac{1}{3}s(s + 1)(2s + 1) < \frac{2}{3}(s + 1)^3 \\ & < \frac{2}{3}\left(\sqrt{n} + 2\right)^3. \end{align*}

• Well, that is reasonable. Thank you for the notices, i appreciate that! Also i've fixed the typos, thanks once again – roman Dec 8 '18 at 20:20