10
$\begingroup$

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!

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

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

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Where does the $1/n$ come from in that integral? $\endgroup$ – Ned Dec 8 '18 at 19:42
  • $\begingroup$ It's $\Delta x$. $\endgroup$ – Bernard Dec 8 '18 at 20:02
  • $\begingroup$ 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. $\endgroup$ – Ned Dec 8 '18 at 20:07
  • 1
    $\begingroup$ @Ned: Sorry, I completely messed up the argumentation. I've fixed that. Thanks for pointing the problem! $\endgroup$ – Bernard Dec 8 '18 at 20:22
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, that is reasonable. Thank you for the notices, i appreciate that! Also i've fixed the typos, thanks once again $\endgroup$ – roman Dec 8 '18 at 20:20

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.