\documentclass{amsart}
\usepackage{amssymb, amsthm}

\newtheorem{thm}{Theorem}

\begin{document}
\title{On an efficient square-root algorithm}
\author{Joel Lewis}
\maketitle

In this paper, we prove the correctness of an algorithm for finding square roots.

\begin{thm}\label{thm:converges}
For any positive number $\alpha$ and any $x_1 > \sqrt{\alpha}$, we may define a sequence $\{x_2, x_3, \ldots\}$ by the recursion formula
\[
x_{n+1} = \frac{1}{2} \left( x_n + \frac{\alpha}{x_n} \right).
\]

Then that $\{x_n\}$ decreases monotonically and $\lim_{n \to \infty} x_n = \sqrt{\alpha}$.
\end{thm}

\begin{proof}We prove this by two inductions.  % First note that since $x_1>0$, $x_n>0$ for all $n$.

Claim 1: $x_n > \sqrt{\alpha}$ for all $n$.  To see this, note it holds for $x_1$, and if $x_k > \sqrt{\alpha}$, then
\begin{align*}
x_{k+1} - \sqrt{\alpha} & = \frac{1}{2} \left( x_k + \frac{\alpha}{x_k} \right) - \sqrt{\alpha} \\
& = \frac{1}{2} (x_k - \sqrt{\alpha})\left(  1- \frac{\sqrt{\alpha} }{x_k} \right) \\
& > 0.
\end{align*}


Claim 2: $x_{n+1} < x_n$ for every $n$.  To see this, first note 
if $x_1 > \sqrt{\alpha}$, then 
\begin{align*}
x_2 & = \frac{1}{2} \left( x_1 + \frac{\alpha}{x_1} \right) \\
& < \frac{1}{2} \left( x_1 + \frac{\alpha}{\sqrt{\alpha}} \right) \\
& = \frac{1}{2} \left( x_1 + \sqrt{\alpha} \right)  \\
& < x_1.
\end{align*}

If $x_k < x_{k-1}$, then
\begin{align*}
x_{k} - x_{k+1} & = \frac{1}{2} \left( x_{k-1} - x_{k} + \frac{\alpha}{x_{k-1}} - \frac{\alpha}{x_k} \right) \\
 & = \frac{1}{2} (x_{k-1} - x_{k} )\left(1 - \frac{\alpha }{x_k x_{k-1}} \right) \\
& >0,
\end{align*}
since $x_kx_{k-1} > \alpha$ by Claim 1.

The sequence $x_n$ is monotone decreasing and bounded below, therefore converges.  To find the limit, note that $x_{n+1}$ and $x_n$ converge to the same thing, say $x$.  Then we have
\[
x = \frac{1}{2} \left( x + \frac{\alpha}{x} \right),
\]
or $x = \sqrt{\alpha}$.
\end{proof}

\begin{thm} Define $\epsilon_n = x_n - \sqrt{\alpha}$.  Then
\[
\epsilon_{n+1} = \frac{ \epsilon_n^2}{2 x_n} < \frac{ \epsilon_n^2}{2 \sqrt{\alpha}},
\]
and so if we set $\beta = 2 \sqrt{\alpha}$ we have
\[
\epsilon_{n+1} < \beta \left( \frac{ \epsilon_1}{\beta} \right)^{2^n}.
\]
\end{thm}

\begin{proof} It was show in the proof of Theorem \ref{thm:converges} that
\begin{align*}
x_{n+1} - \sqrt{\alpha} & = \frac{1}{2} \left( x_n + \frac{\alpha}{x_n} \right) - \sqrt{\alpha} \\
& = \frac{1}{2} \left(x_n - 2\sqrt{\alpha} + \frac{\alpha}{x_n}\right) \\
& =  \frac{1}{2} \left((x_n - \sqrt{\alpha}) + \left( -\sqrt{\alpha} + \frac{\alpha}{x_n}\right)\right) \\
& = \frac{1}{2} \left(x_n\left(1 - \frac{\sqrt{\alpha}}{x_n}\right) - \sqrt{\alpha}\left(1 - \frac{\sqrt{\alpha}}{x_n}\right)\right) \\
& = \frac{1}{2} (x_n - \sqrt{\alpha})\left(  1- \frac{\sqrt{\alpha} }{x_n} \right) \\ 
& = \frac{1}{2} \frac{(x_n - \sqrt{\alpha})^2 }{x_n} \\
& = \frac{\epsilon_n^2}{2 x_n},
\end{align*}
and $x_n > \sqrt{\alpha}$ for every $n$, which gives the stated inequality.  The rest follows by induction.
\end{proof}


\end{document}
