convergence of arithmetic-geometric mean

In this entry, we show that the arithmetic-geometric mean converges.By the arithmetic-geometric means inequality, we know that the sequencesof arithmetic and geometric means are both monotonic and bounded, sothey converge individually. What still needs to be shown is that theyconverge to the same limit.

Define $x_{n}=a_{n}/g_{n}$ . By the arithmetic-geometric inequality, wehave $x_{n}\\geq 1$ . By the defining recursions, we have

x_{n+1}={a_{n+1}\\over g_{n+1}}={a_{n}+g_{n}\\over 2\\sqrt{a_{n}g_{n}}}={1\\over 2%}\\left(\\sqrt{a_{n}\\over g_{n}}+\\sqrt{g_{n}\\over a_{n}}\\right)={1\\over 2}\\left(%\\sqrt{x_{n}}+{1\\over\\sqrt{x_{n}}}\\right)

Since $x_{n}\\geq 1$ , we have $1/\\sqrt{x_{n}}\\leq 1$ , and $\\sqrt{x_{n}}\\leq x_{n}$ , hence

x_{n+1}-1={1\\over 2}\\left(\\sqrt{x_{n}}+{1\\over\\sqrt{x_{n}}}-2\\right)\\leq{1%\\over 2}({x_{n}}+1-2)\\leq{1\\over 2}(x_{n}-1).

From this inequality

0\\leq x_{n+1}-1\\leq{1\\over 2}(x_{n}-1),

we may conclude that $x_{n}\\to 1$ as $n\\to\\infty$ , which , by the definition of $x_{n}$ ,is equivalent to

\\lim_{n\\to\\infty}g_{n}=\\lim_{n\\to\\infty}a_{n}.

Not only have we proven that the arithmetic-geometric mean converges, but we can infera rate of convergence from our proof. Namely, we have that $0\\leq x_{n}-1\\leq(x_{0}-1)/2^{n}$ . Hence, we see that the rate of convergence of $a_{n}$ and $g_{n}$ to the answer goesas $O(2^{-n})$ .

By more carefully bounding the recursion for $x_{n}$ above, we may obtain better estimatesof the rate of convergence. We will now derive an inequality. Suppose that $y\\geq 0$ .

	$\\displaystyle 0$	$\\displaystyle\\leq y^{5}+y^{4}+4y^{3}+3y^{2}$
	$\\displaystyle y^{2}+4y+4$	$\\displaystyle\\leq y^{5}+y^{4}+4y^{3}+4y^{2}+4y+4$
	$\\displaystyle(y+2)^{2}$	$\\displaystyle\\leq(y+1)(y^{2}+2)^{2}$

Set $x=y+1$ (so we have $x\\geq 1$ ).

	$\\displaystyle(x+1)^{2}$	$\\displaystyle\\leq x((x-1)^{2}+2)^{2}$
	$\\displaystyle x$	$\\displaystyle\\leq{x^{2}((x-1)^{2}+2)^{2}\\over(x+1)^{2}}$
	$\\displaystyle\\sqrt{x}$	$\\displaystyle\\leq{x((x-1)^{2}+2)\\over x+1}$
	$\\displaystyle{x+1\\over x}\\sqrt{x}$	$\\displaystyle\\leq(x-1)^{2}+2$
	$\\displaystyle{1\\over 2}\\left(\\sqrt{x}+{1\\over\\sqrt{x}}\\right)$	$\\displaystyle\\leq 1+{1\\over 2}(x-1)^{2}$

Thus, because $x_{n+1}=(\\sqrt{x_{n}}+1/\\sqrt{x_{n}})/2$ , we have

x_{n+1}-1\\leq{1\\over 2}(x_{n}-1)^{2}.

From this equation, we may derive the bound

x_{n}-1\\leq\\frac{1}{2^{2^{n}-1}}(x_{0}-1)^{2^{n}}.

This is a much better bound! It approaches zero far more rapidlythan any exponential function, so we have superlinear convergence.