Convergence of a sequence (possibly Riemann sum)

Solution 1:

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.

Solution 2:

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.

Solution 3:

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