# Rate of convergence of a sequence

I was just playing around rediscovering calculus (trying to figure out the derivative of $\arcsin x$) when I stumbled upon this rather untrivial problem.

$\large \int _0^1 \frac{dx}{\sqrt{1-x^2}} = \frac{\pi}{2}$

From this formula we can apply the definition of definite integral and get the following:

$\large \lim\limits_{m \to \infty} \sum_{i=0}^{m-1} \frac{1}{\sqrt{m^2-i^2}} = \frac{\pi}{2}$

All this is fine, but what is especially interesting is how rapidly does this sequence converge to $\frac{\pi}{2}$? Let us define sequence $N_m:$

$\large {N}_m = \left \lfloor -\log_{10} \left | \frac{\pi}{2} - \sum_{i=0}^{m-1} \frac{1}{\sqrt{m^2-i^2}} \right |\right \rfloor$

So the problem can be formulated as follows: find $m$ such that $N_m \geq k$.

Is it possible to find the exact solution using school grade math? Is it possible to get an approximate estimate?

• It likely converges slowly due to the half order pole at $x=1$. – Simply Beautiful Art Jul 2 '17 at 12:01
• For much faster convergence/approximation of the integral, use: $$\int_0^1\frac1{\sqrt{1-x^2}}~\mathrm dx=\int_0^a\frac1{\sqrt{1-x^2}}~\mathrm dx+\int_a^1\frac1{\sqrt{1-x^2}}~\mathrm dx\\\approx\int_0^a\frac1{\sqrt{1-x^2}}~\mathrm dx+\int_a^1\frac1{\sqrt{2(1-x)}}~\mathrm dx$$ – Simply Beautiful Art Jul 2 '17 at 12:37

Since the integrand is unbounded at $x = 1$, it is not Riemann integrable and the integral is improper:

$$\int_0^1 \frac{dx}{\sqrt{1 - x^2}} = \lim_{c \to 1}\int_0^c \frac{dx}{\sqrt{1 - x^2}} = \frac{\pi}{2}.$$

In general, there is no guarantee that a Riemann sum converges to the improper integral. Fortunately, the integrand is monotonically increasing and in this case it can be shown that the left Riemann sums will converge:

$$\lim_{m \to \infty} \sum_{k=0}^{m-1} \frac{1}{\sqrt{m^2 - k^2}} = \frac{\pi}{2}.$$

If the integrand were continuously differentiable (and Riemann integrable) then the Riemann sums would converge at the rate $O(1/m)$. In this case, the convergence will be at the slower rate $\mathbf{O(1/\sqrt{m})}$.

This convergence rate implies that the approximation error should be reduced roughly by a factor of $2$ as the number of points $m$ increases by a factor of $4$, as you should see by some numerical experimentation.

To see why analytically, observe that

$$\frac{1}{\sqrt{2}}\int_0^1 \frac{dx}{\sqrt{1 - x}} < \int_0^1 \frac{dx}{\sqrt{1 - x^2}} = \int_0^1 \frac{dx}{\sqrt{1 +x}\sqrt{1 - x}} < \int_0^1 \frac{dx}{\sqrt{1 - x}},$$

and we expect the behavior to be similar in terms of convergence to

$$\int_0^1 \frac{dx}{\sqrt{1 -x}} = \int_0^1 \frac{dx}{\sqrt{x}} = 2.$$

In this case, the right Riemann sums are convergent as

$$\lim_{m \to \infty} \frac{1}{m} \sum_{k = 1}^m \frac{1}{\sqrt{k/m}} = \lim_{m \to \infty} \frac{1}{\sqrt{m}} \sum_{k = 1}^m \frac{1}{\sqrt{k}} = 2.$$

Since,

$$2(\sqrt{k+1} - \sqrt{k}) = \frac{2}{\sqrt{k+1} + \sqrt{k}} < \frac{1}{\sqrt{k}} < \frac{2}{\sqrt{k} + \sqrt{k-1}} = 2(\sqrt{k} - \sqrt{k-1}),$$

we can bound the sum as

$$2(\sqrt{m+1} - 1) < \sum_{k=1}^m \frac{1}{\sqrt{k}} < 2 \sqrt{m},$$

and

$$2\left(\sqrt{1 + 1/m} - 1/\sqrt{m}\right) < \frac{1}{\sqrt{m}}\sum_{k=1}^m \frac{1}{\sqrt{k}} < 2.$$

Expanding $\sqrt{1 + 1/m}$ in a Taylor series we find the error behaves as

$$\left|\frac{1}{\sqrt{m}}\sum_{k=1}^m \frac{1}{\sqrt{k}} - 2 \right| = O(1/\sqrt{m})$$