How to evaluate the sum $\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{2n}}+\cdots+\frac{1}{\sqrt{n^2}}$ when $n$ grows?

I need help with the following limit $$\lim_{n\to\infty}\sum_{k=1}^n \frac{1}{\sqrt{kn}}$$

Thanks.

-

Notice for large $n$, we expect $\displaystyle \sum_{k=1}^n \frac{1}{\sqrt{k}} \text{ behave like }\int_1^n \frac{dx}{\sqrt{x}} \sim 2\sqrt{n}$. This suggests $$\frac{1}{\sqrt{k}} \sim \int_{k-1/2}^{k+1/2} \frac{dx}{\sqrt{x}} \sim 2\left( \sqrt{k+\frac12} - \sqrt{k-\frac12}\right)$$ and the terms $\displaystyle \frac{1}{\sqrt{kn}}$ in the summands is close to something "telescopable". To make this idea concrete, we observe: \begin{align} \sum_{k=1}^n\frac{1}{\sqrt{kn}} \ge & \sum_{k=1}^n \frac{2}{\sqrt{n}(\sqrt{k+1}+\sqrt{k})} = \frac{2}{\sqrt{n}} \sum_{k=1}^n(\sqrt{k+1}-\sqrt{k}) = 2 \Big(\sqrt{1+\frac{1}{n}} - \frac{1}{\sqrt{n}}\Big)\\ \sum_{k=1}^n\frac{1}{\sqrt{kn}} \le & \sum_{k=1}^n \frac{2}{\sqrt{n}(\sqrt{k}+\sqrt{k-1})} = \frac{2}{\sqrt{n}}\sum_{k=1}^n(\sqrt{k}-\sqrt{k-1}) = 2 \end{align}

As a result, $$\left|\;\sum_{k=1}^n \frac{1}{\sqrt{kn}} - 2\;\right| \le 2 \left(1+\frac{1}{\sqrt{n}} -\sqrt{1+\frac{1}{n}}\right) < \frac{2}{\sqrt{n}} \quad\implies\quad \lim_{n\to\infty} \sum_{k=1}^n \frac{1}{\sqrt{kn}} = 2.$$

-
+1 Nice. An informal motivation would be to note that (for large $k$, using first order Taylor expansion) $\sqrt{k+1} \approx \sqrt{k} + 1/(2\sqrt{k})$, or $1/\sqrt{k} \approx 2(\sqrt{k+1} - \sqrt{k})$ which can be regarded as a discrete analogous to the derivative $(2\sqrt{x})' = 1/\sqrt{x}$ – leonbloy Sep 2 '13 at 15:12

Your sum can be interpreted as a Riemann sum:

$$\sum_{k=1}^n \frac{1}{\sqrt{kn}} = \frac1n \sum_{k=1}^n \sqrt{\frac{n}{k}}.$$

Let $f(x) = 1/\sqrt{x}$ and let $x_k = k/n$. Then $$\sum_{k=1}^n \frac{1}{\sqrt{kn}} = \frac1n \sum_{k=1}^n \sqrt{\frac{n}{k}} = \frac1n \sum_{k=1}^n f(x_k) \to \int_0^1 f(x)\,dx$$ as $n \to \infty$.

(Since the integral is improper, a little care is needed to justify the last step.)

-
How we can justify the last step? – Pedro Sep 2 '13 at 13:07
So we need to prove that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^nf(x_k)=\lim_{\varepsilon\to 0^+}\left(\lim_{n\to\infty}\frac{(1-\varepsilon)}{n}\sum_{k=1}^nf(x_k)\right)$$ Right? – Pedro Sep 2 '13 at 13:33
A good idea. The caution at the end is a good one ... Riemann sums for a convergent improper integral may or may not go to the value of the integral. – GEdgar Sep 2 '13 at 13:42
@GEdgar At first, we don't konw if $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^nf(x_k)$$ converges (thus limit properties are not valid). So, how we can to prove the equality above? – Pedro Sep 2 '13 at 13:56
This method is well known on physics community. It goes like this: $\xi \equiv k/n$. $\Delta\xi = 1/n \Longrightarrow n\Delta\xi = 1$. Then, $\displaystyle{\sum_{1}^{n}\left(kn\right)^{-1/2} = \sum_{1}^{n}\left(n\xi n\right)^{-1/2}n\,\Delta\xi \to \int_{1}^{\infty}\xi^{-1/2}\,{\rm d}\xi}$ ( when $n \to \infty$ ) which is the quite fine @mrf answer. – Felix Marin Sep 2 '13 at 16:16

mrf has the main idea. But since the integral is improper (as mrf notes) some care is required. Here is one way, using the Lebesgue theory...

Let $f(x) = 1/\sqrt{x}$. For fixed $n$, let $g_n$ be defined by $g_n(x) = \sqrt{n/k}$ for $(k-1)/n < x \le k/n$. Then $0 < g_n(x) \le f(x)$ and $g_n(x) \to f(x)$ on $(0,1]$. Since $f$ is Lebesgue integrable on $(0,1]$, we have by the dominated convergence theorem $\int_0^1 g_n \to \int_0^1 f$. That is: $$\frac{1}{n}\sum_{k=1}^n\sqrt{\frac{n}{k}} \to \int_0^1 \frac{dx}{\sqrt{x}}$$

ASIDE

Monthly problem 11376 has an example of how blindly saying "Riemann sum" can lead one astray. The solution is on p. 238 of the March, 2010 issue. The problem defines $$S_n(a) = \sum_{an \lt k \le (a+1)n}\frac{1}{\sqrt{kn-an^2}\;}$$ for real $a$ and positive integer $n$, and asks for which $a$ does $\lim_{n \to \infty} S_n(a)$ exist. Many solvers noted that $S_n(a)$ is a Riemann sum for $$\int_a^{a+1} \frac{dx}{\sqrt{x-a}\;} = 2$$ and then carelessly concluded that $S_n(a) \to 2$ for all $a$. But, in fact, as the published solution shows, $S_n(a)$ converges if and only if $a$ is rational.

The problem here is the case $a=0$, and fortunately $0$ is rational.

-
Ha ha! I am one of those who falsely "proved" convergence. – Byron Schmuland Sep 2 '13 at 16:00
As I mentioned in my comment to mrf's answer, I believe that Monotone Convergence also applies since this sequence of functions is pointwise monotone. – robjohn Sep 4 '13 at 15:58
@robjohn: It is not monotone along $n$, but yes it is monotone along $2^n$, say. – GEdgar Sep 4 '13 at 16:07
@GEdgar I would like know how to prove that $S_n(a)$ converges if and only if $a$ is rational. Is it possible you post the solution of this problem? – Pedro Sep 4 '13 at 16:37

Think about $$\int_0^1 f(x)dx,~~~f(x)=\frac{1}{\sqrt{x}}$$

Indeed: $$\int_a^b f(x)dx=\lim_{n\to\infty}\sum_{i=1}^nf\left(a+\frac{b-a}{n}i\right)\left(\frac{b-a}{n}\right)$$

-
I think your solution is valid if $$\lim_{n\to\infty}\sum_{k=1}^nf\left(\frac{i}{n}\right)\frac{b}{n}=\lim_{a\to 0^+}\left(\lim_{n\to\infty}\sum_{k=1}^nf\left(a+\frac{b-a}{n}i\right)\frac{(b-a)‌​}{n}\right)$$ So, how to prove it? – Pedro Sep 2 '13 at 14:16
Nice work, Babak! +1 – amWhy Sep 3 '13 at 0:11