# Hero's Method

## Theorem

Let $a \in \R$ be a real number such that $a > 0$.

Let $x_1 \in \R$ be a real number such that $x_1 > 0$.

Let $\sequence {x_n}$ be the sequence in $\R$ defined recursively by:

$\forall n \in \N_{>0}: x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$

Then $x_n \to \sqrt a$ as $n \to \infty$.

## Lemmata

First we have the following lemmata:

### Lemma 1

$\forall n \in \N_{>0}: x_n > 0$

$\Box$

### Lemma 2

$\forall n \ge 2: x_n \ge \sqrt a$

$\Box$

## Proof 1

Consider $x_n - x_{n + 1}$.

 $\displaystyle x_n - x_{n + 1}$ $=$ $\displaystyle x_n - \frac {x_n + \dfrac a {x_n} } 2$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \paren {x_n^2 - a}$ $\displaystyle$ $\ge$ $\displaystyle 0$ for $n \ge 2$ Lemma 2

So, providing we ignore the first term (about which we can state nothing), the sequence $\sequence {x_n}$ is decreasing and bounded below by $\sqrt a$.

Thus by the Monotone Convergence Theorem (Real Analysis), $x_n \to l$ as $n \to \infty$, where $l \ge \sqrt a$.

Now we want to find exactly what that value of $l$ actually is.

By Limit of Subsequence equals Limit of Real Sequence we also have $x_{n + 1} \to l$ as $n \to \infty$.

But $x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$.

Because $l \ge \sqrt a$ it follows that $l \ne 0$.

So by the Combination Theorem for Sequences:

$x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2 \to \dfrac {l + \dfrac a l} 2$ as $n \to \infty$

Since a Convergent Real Sequence has Unique Limit, that means:

$l = \dfrac {l + \dfrac a l} 2$

and so (after some straightforward algebra):

$l^2 = a$

Thus:

$l = \pm \sqrt a$

and as $l \ge +\sqrt a$ it follows that:

$l = +\sqrt a$

Hence the result.

$\blacksquare$

## Proof 2

Let $a > 0$.

We make no statement about $x_1$.

We specify that:

$x_{n + 1} = \dfrac {x_n + \dfrac a {x_n} } 2$

Now:

 $\displaystyle x_{n + 1} - \sqrt a$ $=$ $\displaystyle \frac {x_n + \dfrac a {x_n} } 2 - \sqrt a$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \paren {x_n^2 - 2 x_n \sqrt a + a}$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \paren {x_n - \sqrt a}^2$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \paren {\dfrac {\paren {x_{n - 1} - \sqrt a}^2} {2 x_{n - 1} } }^2$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \paren {x_{n - 1} - \sqrt a}^4$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \frac 1 {\paren {2 x_{n - 2} }^4} \paren {x_{n - 2} - \sqrt a}^8$ $\displaystyle$ $=$ $\displaystyle \frac 1 {2 x_n} \frac 1 {\paren {2 x_{n - 1} }^2} \cdots \frac 1 {\paren {2 x_1}^{2 n - 1} } \paren {x_1 - \sqrt a}^{2 n}$

If we now assume that $x_1 \ge \sqrt a$, then it follows from Lemma 2 that $x_n \ge \sqrt a$.

So:

 $\displaystyle \size {x_{n + 1} - \sqrt a}$ $\le$ $\displaystyle \paren {\frac 1 {2 \sqrt a} }^{1 + 2 + 2^2 + \cdots + 2^{n - 1} } \paren {x_1 - \sqrt a}^{2 n}$ $\displaystyle$ $=$ $\displaystyle \paren {\frac 1 {2 \sqrt a} }^{\dfrac {2^n - 1} {2 - 1} } \paren {x_1 - \sqrt a}^{2 n}$ $\displaystyle$ $=$ $\displaystyle 2 \sqrt a \paren {\frac {x_1 - \sqrt a} {2 \sqrt a} }^{2 n}$

If $\size y < 1$, then $y^n \to 0$ as $n \to \infty$ from Sequence of Powers of Number less than One.

$y^{2^n} \to 0$ as $n \to \infty$

Thus we see that:

$x_n \to \sqrt a$ as $n \to \infty$

provided that:

$\dfrac {x_1 - \sqrt a} {2 \sqrt a} < 1$

that is, that:

$\sqrt a \le x_1 < 3 \sqrt a$

We assumed above that $x_1 \ge \sqrt a$.

Now we have shown that $x_n \to \sqrt a$ as $n \to \infty$ provided that $\sqrt a \le x_1 < 3 \sqrt a$.

However, we have already shown that $x_n \to \sqrt a$ as long as $x_1 \ge 0$.

The advantage to this analysis is that this gives us an opportunity to determine how close $x_n$ gets to $\sqrt a$.

$\blacksquare$

## Examples

### Square Root of $5$

The calculation of the square root of $5$ by Hero's Method proceeds as follows:

 $\displaystyle x_0$ $=$ $\displaystyle 2$ as the initial approximation $\displaystyle \leadsto \ \$ $\displaystyle x_1$ $=$ $\displaystyle \dfrac {2 + \frac 5 2} 2$ $\displaystyle$ $=$ $\displaystyle 2 \cdotp 25$ $\displaystyle \leadsto \ \$ $\displaystyle x_2$ $=$ $\displaystyle \dfrac {2.25 + \frac 5 {2.25} } 2$ $\displaystyle$ $=$ $\displaystyle 2 \cdotp 236 \, 111 \, 111 \dots$ $\displaystyle \leadsto \ \$ $\displaystyle x_3$ $=$ $\displaystyle \dfrac {2 \cdotp 236 \, 111 \, 111 \dots + \frac 5 {2 \cdotp 236 \, 111 \, 111 \dots} } 2$ $\displaystyle$ $=$ $\displaystyle 2 \cdotp 236 \, 067 \, 978 \dots$ $\displaystyle \leadsto \ \$ $\displaystyle x_4$ $=$ $\displaystyle 2 \cdotp 236 \, 067 \, 978 \dots$

Comparing with Square Root of $5$, we have:

The decimal expansion of $\sqrt 5$ starts:

$\sqrt 5 \approx 2 \cdotp 23606 \, 79774 \, 99789 \, 6964 \ldots$

$\blacksquare$

## Also known as

Some sources report this as Heron's method.

## Source of Name

This entry was named for Heron of Alexandria.