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

Question

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!

Answer 1

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

Answer 2

$\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$.

Answer 3

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[4]{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*}

Answer 4

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.

Answer 5

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$%).

Answer 6

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