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



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
    $\begingroup$ +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}$ $\endgroup$ – 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.)

  • $\begingroup$ How we can justify the last step? $\endgroup$ – Pedro Sep 2 '13 at 13:07
  • $\begingroup$ 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? $\endgroup$ – Pedro Sep 2 '13 at 13:33
  • $\begingroup$ 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. $\endgroup$ – GEdgar Sep 2 '13 at 13:42
  • $\begingroup$ @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? $\endgroup$ – Pedro Sep 2 '13 at 13:56
  • $\begingroup$ 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. $\endgroup$ – 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}} $$


Monthly problem 11376 has an example of how blindly saying "Riemann sum" can lead one astray. The solution is on p. 283 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.

  • $\begingroup$ Ha ha! I am one of those who falsely "proved" convergence. $\endgroup$ – user940 Sep 2 '13 at 16:00
  • $\begingroup$ 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. $\endgroup$ – robjohn Sep 4 '13 at 15:58
  • $\begingroup$ @robjohn: It is not monotone along $n$, but yes it is monotone along $2^n$, say. $\endgroup$ – GEdgar Sep 4 '13 at 16:07
  • $\begingroup$ @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? $\endgroup$ – Pedro Sep 4 '13 at 16:37
  • $\begingroup$ Monthly problem 11376 of what journal? $\endgroup$ – Robin Oct 25 '18 at 15:26

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

  • $\begingroup$ 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? $\endgroup$ – Pedro Sep 2 '13 at 14:16
  • $\begingroup$ Nice work, Babak! +1 $\endgroup$ – Namaste Sep 3 '13 at 0:11

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.