## 3.1. Sequences

### Examples 3.1.10(c): Computing Square Roots

*a > 0*and

*x*and define the recursive sequence

_{0}> 0Show that this sequence converges to the square root ofx_{n+1}=^{1}/_{2}(x_{n}+^{a}/ x_{n})

*a*regardless of the starting point

*x*.

_{0}> 0*x*. Note that the 'true' value of with 12 digits after the period is

_{0}= 2*1.414213562373*. Our recursive sequence would approximate this value quickly as follows:

Term |
Exact Value |
Approximate Value |

x_{0} |
2 | |

x_{1} = ^{1}/_{2} (x_{0} + ^{a} / x_{0}) |
^{1}/_{2} (2 + ^{2}/_{2}) = ^{3}/_{2} |
1.5 |

x_{2} = ^{1}/_{2} (x_{1} + ^{a} / x_{1}) |
^{1}/_{2} (^{3}/_{2} + ^{2}/_{3/2}) = ^{17}/_{12} |
1.416666667 |

x_{3} = ^{1}/_{2} (x_{2} + ^{a} / x_{2}) |
^{1}/_{2} (^{17}/_{12} + ^{2}/_{17/12}) = ^{577}/_{408} |
1.414215686 |

x_{4} = ^{1}/_{2} (x_{3} + ^{a} / x_{3}) |
^{1}/_{2} (^{577}/_{408} + ^{2}/_{577/408}) = ^{665857}/_{470832} |
1.414213562375 |

After only 4 steps our sequence has approximated the 'true' value of with 11 digits accuracy.

Now that we have seen the usefulness of this particular recursive sequence we need
to prove that it really does converge to the square root of *a*.

First, note that *x _{n} > 0* for all

*n*so that the sequence is bounded below.

Next, let's see if the sequence is monotone decreasing, in which case it would have to converge to some limit. Compute

Now let's take a look atx_{n}- x_{n+1}= x_{n}-^{1}/_{2}(x_{n}+^{a}/ x_{n}) =^{1}/_{2}(x_{n}^{2}- a) / x_{n}

*x*:

_{n}^{2}- aBut that means thatx_{n}^{2}- a =^{1}/_{4}(x_{n-1}+^{a}/ x_{n-1})^{2}- a

=^{1}/_{4}x_{n-1}^{2}+^{1}/_{2}a +^{1}/_{4}a^{2}/ x_{n-1}^{2}- a

=^{1}/_{4}x_{n-1}^{2}-^{1}/_{2}a +^{1}/_{4}a^{2}/ x_{n-1}^{2}

=^{1}/_{4}(x_{n-1}-^{a}/ x_{n-1})^{2}

0

*x*, or equivalently

_{n}- x_{n+1}0*x*. Hence, the sequence is monotone decreasing and bounded below by 0 so it must converge.

_{n}x_{n+1}
We now know that
*x _{n} = L*.
To find that limit, we could try the following:

Solving the equation(*) L = x_{n}= x_{n+1}=^{1}/_{2}(x_{n}+^{a}/x_{n}) =^{1}/_{2}(L + a / L)

*L =*gives

^{1}/_{2}(L + a / L)or equivalently2 L^{2}= L^{2}+ a

which means that the limitL^{2}= a

*L*is indeed the square root of

*a*, as required.

However, our proof contains one small caveat. In order to take the limit inside the
fraction in equation (*) we need to know that *L* is not zero *before*
we can write down equation (*). We already know that *x _{n}* is
bounded below by zero, but that is not good enough to exclude the possibility of

*L = 0*. But we have already shown that

so thatx_{n}^{2}- a =^{1}/_{4}(x_{n-1}-^{a}/ x_{n-1})^{2}0

*x*. That implies that the limit of the sequence (which we already know exists) is strictly positive since

_{n}^{2}a*a > 0*. Therefore equation (*) is justified and we have completed the proof.