# Convergence of a sequence (possibly Riemann sum)

Let $a_1, a_2, a_3, . . . , a_n$ be the sequence defined by $$a_n = 2\sqrt{n}-\sum_{k=1}^{n}\frac{1}{\sqrt{k}} = 2\sqrt{n} - \frac{1}{\sqrt{1}}-\frac{1}{\sqrt{2}}-...-\frac{1}{\sqrt{n}}$$

show that the sequence $a_n$ is convergent to some limit L, and that $1<L<2$.

I tried looking at this as a Riemann sum. However, I failed to covert it to that. Any hints on that or alternate solution? Thanks

• @MhenniBenghorbal Any hints on why that is? – codeedoc Mar 28 '14 at 0:47
• Do you know the Euler-Maclaurin formula(s)? If so, then the sum should pop out clearly as an approximation to the integral $\int_1^n x^{-\frac12}\ dx$, and you can use the asymptotic version to estimate how much it varies from that integral (which is of course very nearly the first term $2\sqrt{n}$). See en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula for more details if you don't know the formula. – Steven Stadnicki Mar 28 '14 at 0:54
• Even without E-M, you should be able to look at 'upper' and 'lower' Riemann sums for that integral (hint: $x^{-\frac12}$ is a decreasing function of $x$) and translate them to terms that look much like the sum. – Steven Stadnicki Mar 28 '14 at 0:56
• @StevenStadnicki It is a problem from our calculus competition. Knowledge till calculus 3 should be sufficient. And I don't know how to get k and n together into a Riemann sum. – codeedoc Mar 28 '14 at 1:19
• @MhenniBenghorbal, the limit isn't $2$, unfortunately. – Antonio Vargas Mar 28 '14 at 1:44

## 4 Answers

Here's an elementary solution that uses calculus and one fact from analysis -- a bounded increasing sequence converges.

First, I claim that $a_n$ is strictly increasing. To see why, calculate the difference $a_{n+1}-a_n$: \begin{align} a_{n+1}-a_n &= 2\sqrt{n+1}-2\sqrt{n} - \frac{1}{\sqrt{n+1}} \\ &= 2(\sqrt{n+1}-\sqrt n)\cdot\frac{\sqrt{n+1}+\sqrt n}{\sqrt{n+1} + \sqrt n} - \frac{1}{\sqrt{n+1}} \\ &= \frac{2}{\sqrt{n+1}+\sqrt n}-\frac{1}{\sqrt{n+1}} > 0. \end{align} The last inequality follows from the inequality $\frac{1}{2}(\sqrt{n+1}+\sqrt n)<\sqrt{n+1}$. It follows that $a_n$ is strictly increasing, and we conclude that $a_n>1=a_1$ for $n>1$.

Next, we're going to put upper and lower asymptotic bounds on $a_n$, as follows. Letting $S_n=\sum_{k=1}^n k^{-1/2}$, I claim that $$2\sqrt{n+1} - 2 < S_n < 2\sqrt n.$$ Proving this inequality will actually finish the problem: if we subtract $2\sqrt n$ from all parts of the inequality and multiply by $-1$, we get $$2-2(\sqrt{n+1}-\sqrt n) > a_n > 0.$$ This means that $a_n$ is bounded above, and therefore converges because we showed that it is strictly increasing. Taking the limit as $n\to\infty$ and writing $L=\lim_{n\to\infty} a_n$, we see that $2\geq L$. Then $1 < L \leq 2$. (With a finer analysis, you may be able to replace the $\leq$ with a $<$. My solution is not entirely satisfactory to that extent: can anyone offer an improvement?)

One way to find these bounds is to approximate the sum $S_n$ by integrals; a second way is to cleverly bound $k^{-1/2}$. I'll show you the first approach since it's probably what the question-writer wanted, and I'll show you the second because it's so slick.

To derive the bounds with integrals, start with the following integral inequality: $$\int_0^n x^{-1/2}\,dx < \sum_{k=1}^n k^{-1/2} < \int_1^{n+1} x^{-1/2}\,dx.$$ If you haven't seen this sort of thing before, let me know and I'll be happy to explain. You can understand why this works by drawing the right picture. In any case, if you evaluate these integrals you'll produce the bound on $S_n$.

To derive the bounds with cleverness, start with the following square root inequality: $$\frac{2}{\sqrt{k+1}+\sqrt{k}} < \frac{1}{\sqrt k} < \frac{2}{\sqrt{k} + \sqrt{k-1}}.$$ Completing the square on the left and right transforms the inequality into $$2(\sqrt{k+1}-\sqrt{k}) < \frac{1}{\sqrt k} < 2(\sqrt{k}-\sqrt{k-1}).$$ Summing this inequality from $k=1$ to $k=n$ -- it telescopes -- yields $$2\sqrt{n+1} - 2 < S_n < 2\sqrt n,$$ as desired.

Here's a neat method from de Bruijn's book*. $\DeclareMathOperator{rre}{Re}$

Let $z$ be a complex parameter with $\rre z > 0$, $z \neq 1$. By telescoping we have

$$\sum_{k=1}^{n} k^{-z} = \frac{n^{1-z}}{1-z} + \sum_{k=1}^{n} \left(k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right).$$

The sum on the right converges as $n \to \infty$ since

$$k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z} \sim - \frac{z}{2} k^{-1-z}$$

as $k \to \infty$, so we can write

$$\sum_{k=1}^{n} k^{-z} = \frac{n^{1-z}}{1-z} + \sum_{k=1}^{\infty} \left(k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right) + \epsilon_n(z), \tag{1}$$

where $\epsilon_n(z) \to 0$ as $n \to \infty$ for fixed $z$. We'll show at the end of the answer that the sum

$$S(z) := \sum_{k=1}^{\infty} \left(k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right)$$

is analytic in the region $\rre z > 0$, $z \neq 1$. Taking $\rre z > 1$ and sending $n \to \infty$ in $(1)$ we find that

$$S(z) = \sum_{k=1}^{\infty} k^{-z} = \zeta(z),$$

so by analytic continuation we must also have $S(z) = \zeta(z)$ for all $z$ with $\rre z > 0$, $z \neq 1$. Equation $(1)$ can therefore be written

$$\sum_{k=1}^{n} k^{-z} = \frac{n^{1-z}}{1-z} + \zeta(z) + \epsilon_n(z). \tag{2}$$

Taking $z = 1/2$ in $(2)$ yields

$$\sum_{k=1}^{n} \frac{1}{\sqrt{k}} = 2\sqrt{n} + \zeta(1/2) + \epsilon_n(1/2),$$

so we may conclude that

$$\lim_{n \to \infty} 2\sqrt{n} - \sum_{k=1}^{n} \frac{1}{\sqrt{k}} = -\zeta(1/2).$$

Now let's prove that

$$S(z) = \sum_{k=1}^{\infty} \left(k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right)$$

is analytic in the region $\rre z > 0$, $z \neq 1$. It suffices to show that the sum converges uniformly with respect to $z$ as long as $z$ remains in a compact subset of $\rre z > 0$, $z \neq 1$. Indeed, sequences of analytic functions which converge uniformly on all compact subsets of a domain converge to an analytic function on that domain.

To start let's write

$$k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z} = \frac{k^{1-z}}{1-z} \left[\left(1-\frac{1}{k}\right)^{1-z} - 1 + \frac{1-z}{k}\right]. \tag{3}$$

The term in brackets is none other than the function $f(w) := (1-w)^{1-z}$ minus the first two terms of its Maclaruin series and evaluated at $w = 1/k$. We therefore expect a bound like

$$\left|f(w) - \sum_{j=0}^{1} \frac{f^{(j)}(0)}{j!}w^j\right| \leq Cw^2 = \frac{C}{k^2},$$

and we just need to show that $C$ can be chosen independently of $z$.

If the Maclaurin series for a function $f$ has radius of convergence $R > 0$ then (after some work) it follows from Cauchy's integral theorem that

$$f(w) - \sum_{j=0}^{N} \frac{f^{(j)}(0)}{j!} w^j = \frac{w^{N+1}}{2\pi i} \int_C \frac{f(\zeta)}{\zeta^{N+1}(\zeta - w)}\,d\zeta,$$

where $C$ is the circle $|\zeta| = r < R$ and $|w| < r$. So, taking $f(w) = (1-w)^{1-z}$, $N = 1$, $w = 1/k$, and $r = 1/2$ we have, for $k \geq 3$,

$$\left(1-\frac{1}{k}\right)^{1-z} - 1 + \frac{1-z}{k} = \frac{1}{2\pi i k^2} \int_{|\zeta| = 1/2} \frac{(1-\zeta)^{1-z}}{\zeta^2 (\zeta - 1/k)}\,d\zeta.$$

Now assume $\rre z \geq \delta$ and $|1-z| \geq \delta$ for some $0 < \delta < 1$. By taking the modulus of the above equation we get

\begin{align} \left|\left(1-\frac{1}{k}\right)^{1-z} - 1 + \frac{1-z}{k}\right| &= \left|\frac{1}{2\pi i k^2} \int_{|\zeta| = 1/2} \frac{(1-\zeta)^{1-z}}{\zeta^2 (\zeta - 1/k)}\,d\zeta\right| \\ &\leq \frac{1}{2\pi k^2} \int_{|\zeta| = 1/2} \frac{|1-\zeta|^{1-\rre z}}{|\zeta|^2 |\zeta - 1/k|}\,|d\zeta| \\ &\leq \frac{1}{2\pi k^2} \int_{|\zeta| = 1/2} \frac{2}{(1/2)^2 (1/2 - 1/3)}\,|d\zeta| \\ &= \frac{2}{2\pi (1/2)^2 (1/2-1/3)k^2} \int_{|\zeta| = 1/2} |d\zeta| \\ &= \frac{2 \pi}{2\pi (1/2)^2 (1/2-1/3)k^2} \\ &= \frac{24}{k^2}. \end{align}

Combining this with $(3)$ yields

\begin{align} \left|k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right| &= \frac{k^{1-\rre z}}{|1-z|} \left|\left(1-\frac{1}{k}\right)^{1-z} - 1 + \frac{1-z}{k}\right| \\ &\leq \frac{k^{1-\delta}}{\delta} \left|\left(1-\frac{1}{k}\right)^{1-z} - 1 + \frac{1-z}{k}\right| \\ &\leq \frac{24}{\delta} k^{-1-\delta} \end{align}

for $k \geq 3$, which is what we wanted to show. It follows that the series

$$\sum_{k=1}^{\infty} \left(k^{-z} - \frac{k^{1-z}}{1-z} + \frac{(k-1)^{1-z}}{1-z}\right)$$

converges uniformly in the region $\{z \in \mathbb C : \rre z \geq \delta \text{ and } |1-z| \geq \delta\}$ for every $\delta > 0$ and hence that $S(z)$ is analytic in the region $\rre z > 0$, $z \neq 1$.

* N. G. de Bruijn, Asymptotic Methods in Analysis, section 3.5.

• Very nice answer! I wonder if there is an intuition behind this method, or if this is a subproduct of a more sophisticated theorem. Anyway, great solution. – mookid Mar 28 '14 at 5:23
• @mookid, this is a little similar to the method of introducing a parameter into an integral (then taking advantage of its differentiability with respect to it), I suppose. – Antonio Vargas Mar 28 '14 at 13:48
• @mookid, you may also be interested in this blog post by Terry Tao. – Antonio Vargas Mar 28 '14 at 16:10

This is maybe is little off-topic, but we can prove convergence and give an expression for the limit at the same time.

Let us note $\delta_n = a_n - a_{n-1} =2\sqrt{n} - 2\sqrt{n-1} - \frac 1{\sqrt{n}}$.

Now use the fact that $\sqrt{}$ is analytic on $[0,1]$:

$$\sqrt{1-z} = \sum_{m=0}^\infty \frac{(2m)!}{(m!)^2(1-2m)} \left(\frac z{4}\right)^m \\ \sqrt{n-1} - \sqrt{n} = \sqrt{n}\left(\sqrt{1-\frac 1n}-1\right) =\sqrt{n} \sum_{m=1}^\infty \frac{(2m)!}{(m!)^2(1-2m)} \left(\frac 1{4n}\right)^m \\ \delta_n = -\frac 1{\sqrt{n}} -2(\sqrt{n-1} - \sqrt{n}) =2\sqrt{n} \sum_{m=2}^\infty \frac{(2m)!}{(m!)^2(2m-1)} \left(\frac 1{4n}\right)^m.$$ Now everything is positive and we can use the Fubini–Tonelli theorem:

$$\sum_{n=1}^\infty \delta_n = 2 \sum_{m=2}^\infty \frac{(2m)!}{(m!)^2(2m-1)4^m} \zeta\left(m-\frac12\right)<\infty,$$

because $\zeta\left(m-\frac12\right)$ is decreasing and hence bounded, and for the remaining series the Stirling formula yields: $$\frac{(2m)!}{4^m(m!)^2(2m-1)} \sim \frac{2^{2m} m^{2m} e^{-2m}\sqrt{4\pi m}} {4^m m^{2m} e^{-2m} 2\pi m\times 2m} =\frac 1{\sqrt{\pi} m^{3/2}};\\ \sum m^{-3/2}<\infty.$$

Here is an approach. I introduced a closed form for the more general case in a previous problem

$$\sum_{i=1}^{n} i^s = \sum_{i=1}^{\infty}i^s - \sum_{i=0}^{\infty}(i+n+1)^s = \zeta(-s) - \zeta(-s, n+1)\,,$$

which gives

$$\sum_{i=1}^{n} i^{1/2} = \zeta(-1/2) - \zeta(-1/2, n+1)$$

$$\implies 2\sqrt{n}-\sum_{i=1}^{n} i^{1/2} =2\sqrt{n} -\zeta(-1/2) + \zeta(-1/2, n+1) .$$

Now, to find the limit as $n$ goes to $\infty$ you need to use the identity $25.11.43$.