13
$\begingroup$

In many of the standard textbooks discussing Real Numbers, the Cauchy sequence that converges to $\sqrt{2}$ is given as

1, 1.4, 1.41, 1.414, 1.4142, ...

or

2, 1.5, 1.42, 1.415, 1.4143, ...

My question is how are these sequences generated? In other words, if I have 1, 1.4, 1.41 how do I figure out that the next element of the sequence is 1.414?

$\endgroup$
  • 2
    $\begingroup$ You are asking you would find the decimal approximation of a given number, say $\sqrt{2}$? $\endgroup$ – Guy May 29 '17 at 14:34
  • 7
    $\begingroup$ There are different algorithms for calculating the decimals for $\sqrt{2}$. Each algorithm will give a sequence of numbers approximating it. Even though some of these sequences are different, they all have the same limit. $\endgroup$ – Joe Johnson 126 May 29 '17 at 14:39
  • 3
    $\begingroup$ For the recursive notation of your sequence is $a_1=2$, and $a_{n+1}=\frac{1}{2} \Bigl(a_n+\frac{2}{a_n} \Bigr)$ $\endgroup$ – Chinnapparaj R May 29 '17 at 14:41
  • 8
    $\begingroup$ As food for thought, the sequences $(1/n)_{n\in\Bbb{N}}$, $(1/2n)_{n\in\Bbb{N}}$ and $\{0,0,0,...\}$ all converge to zero, yet they're different. $\endgroup$ – AspiringMathematician May 29 '17 at 14:43
  • 2
    $\begingroup$ @Chinz Neither sequence given by OP is that one. $\endgroup$ – Travis May 29 '17 at 14:49
26
$\begingroup$

The following is an example of a method that you could use to figure this out. The method is called bisection. It is not the fastest, but it is clear how to extract digits from it because it has explicit error bounds.

You know $1^2<2$. You know $2^2>2$. So $1<\sqrt{2}<2$ so its first decimal digit is $1$.

You check $1.5^2>2$. You check $1.25^2<2$. You check $1.375^2<2$. You check $1.4375^2>2$. You check $1.40625^2<2$. Now you know $1.40625<\sqrt{2}<1.4375$ so you know the first two digits are $1.4$.

You continue: you check $1.421875^2>2$. You check $1.4140625^2<2$. You check $1.41796875^2>2$. So $1.4140625<\sqrt{2}<1.41796875$, so you know the first three decimal digits now.

You can keep going; at each time you know $\sqrt{2}$ is in between two numbers getting closer together, so as soon as those numbers have a new digit in common, you know that digit of $\sqrt{2}$. On average it takes $\log_2(10) \approx 3.3$ steps to get a new correct decimal digit.

At the cost of slightly more iterations, you can make calculations easier (if you're doing it by hand) by rounding the lower bound down and/or the upper bound up. For instance back in the second paragraph of iterations you could have said $1.4<\sqrt{2}<1.44$ and then continued, obtaining $1.41<\sqrt{2}<1.415$ at the end of the third paragraph.

$\endgroup$
  • 5
    $\begingroup$ If it's the decimal digits that you're after, it's much simpler to do an asymmetric bisection, truncating the candidates to the current length: after $1.5$, check $1.2$ (or $1.3$ according to taste), then $1.4$ etc. This gives you the second digit. Then you try $1.45$, $1.42$, $1.41$ to get the third digit. And so on. $\endgroup$ – TonyK May 29 '17 at 19:20
  • 1
    $\begingroup$ @TonyK Yes, I thought of mentioning something along these lines but just decided against it since the answer was already long. But you can potentially add in a significant number of iterations this way. For example, going from $1.4 < \sqrt{2} < 1.44$ to $1.41$ takes 3 iterations. Going from $1.4 < \sqrt{2} < 1.5$ to $1.41$ takes 4. Also, on a computer, until you've already reached double precision, there is no loss of time per iteration using all the digits. $\endgroup$ – Ian May 29 '17 at 19:26
  • $\begingroup$ The trouble is, your method doesn't give you the digits $-$ that requires extra work. (If you are worried about performance, do a bisection search three digits at a time. $1000$ is nearly $1024$, so this is almost optimal in number of steps required, and so will end up faster because there is no further work to do.) $\endgroup$ – TonyK May 29 '17 at 19:44
  • $\begingroup$ @TonyK It's pretty modest postprocessing, if numbers are stored in decimal form. Keep track of what digit you're working on, and when they become the same you spit out a digit and advance the digit counter. But yes, exploiting close powers of 2 and 10 gives more efficiency...while other methods entirely give dramatically more efficiency even than that. Newton for example is quite excellent but using it for digit extraction is a bit more involved (you basically run two parallel Newton methods). $\endgroup$ – Ian May 29 '17 at 20:08
  • $\begingroup$ Isnt it called interpolation $\endgroup$ – bleh May 29 '17 at 23:01
15
$\begingroup$

In general, without more information one cannot produce a term in a sequence using just its previous terms.

One can describe where both of these particular sequences come from, however:

The first comes from truncating the decimal expansion of $\sqrt{2}$ at each successive decimal place. One can give an easy explicit formula for this:

$$a_n := 10^{-n} \lfloor 10^n \sqrt{2} \rfloor .$$

The second is similar, but instead of truncating, i.e., rounding down the nearest number whose decimal expansion has $\leq n$ digits, one rounds up:

$$a_n := 10^{-n} \lceil 10^n \sqrt{2} \rceil .$$

There are infinitely many more Cauchy sequences with limit $\sqrt{2}$. One uses the so-called Babylonian Method, which is itself a specialization of Newton's Method. In this case the terms are defined iteratively, by $$a_n := \frac{1}{2}\left(a_{n - 1} + \frac{2}{a_{n - 1}}\right) ,$$ where we can take $a_0$ to be any suitable value. Taking the convenient value $a_0 = 2$ gives the sequence $$2, \frac{3}{2}, \frac{17}{12}, \frac{577}{408}, \ldots ,$$ which converges relatively quickly.

$\endgroup$
6
$\begingroup$

Not the numbers in the question, but the integral

$$\int_0^1 \frac{x^m(1-x)^n}{\sqrt{1+x}}dx$$

produces rational approximations to $\sqrt{2}$ from above for $m$ odd and from below for $m$ even.

Some of the approximations for small $m,n$ include

$$\frac{1}{2}\int_0^1 \frac{1}{\sqrt{1+x}}dx =\sqrt{2} -1 $$ $$\frac{3}{2}\int_0^1 \frac{x}{\sqrt{1+x}}dx = 2 - \sqrt{2}$$ $$\frac{3}{8}\int_0^1 \frac{1-x}{\sqrt{1+x}}dx = \sqrt{2}-\frac{5}{4}$$ $$\frac{5}{8}\int_0^1 \frac{x(1-x)}{\sqrt{1+x}}dx=\frac{3}{2}-\sqrt{2}$$

$$\frac{21}{64}\int_0^1 \frac{x(1-x)^2}{\sqrt{1+x}}dx=\frac{23}{16}-\sqrt{2}$$

$$\frac{315}{832}\int_0^1 \frac{x^2(1-x)^2}{\sqrt{1+x}}dx = \sqrt{2}-\frac{73}{52}$$

Another way to obtain approximations converging to $\sqrt{2}$ comes from setting $x=1$ into the expansion for $\sqrt{1+x}$, which yields

$$\sqrt{2}=1+\frac{1}{2}-\frac{1}{8}+\frac{1}{16}-\frac{5}{128}+\frac{7}{256}...$$

This expansion and many more methods can be found in Pythagoras' Constant: $\sqrt{2}$ by Gourdon and Sebah. For instance, example 9, due to Euler,

$$\sqrt{2}=\frac{7}{5}\sum_{n=0}^\infty \frac{(2n)!}{(n!)^2 200^n}$$

produces exactly $1.4, 1.414, 1.41421$ when truncating to $1, 2$ and $3$ terms, and it provides about two correct decimal digits per term.

Finally, the Egyptian fraction described in the Wikipedia can be written in closed form using Paolo Lava's formula for sequence https://oeis.org/A082405.

$$\sqrt{2}=\frac{3}{2}-\sum_{k=0}^\infty \frac{2\sqrt{2}}{(17+12\sqrt{2})^{2^k}-(17-12\sqrt{2})^{2^k}}$$

The first approximations produced are $$\frac{3}{2},\frac{17}{12},\frac{577}{408},\frac{665857}{470832}, \frac{886731088897}{627013566048},\frac{1572584048032918633353217}{1111984844349868137938112},$$

so this may be a series equivalent form of Newton's iteration.

$\endgroup$
4
$\begingroup$

The fast, sensible way to find approximations to $\sqrt2$ is to use the ancient Babylonian method illustrated in Travis's answer. Another way to do it is to use continued fractions. The continued fraction representation of $\sqrt2$ is very simple. In fact, all quadratic irrational numbers have continued fraction representations that eventually repeat.

The partial evaluations of a continued fraction are called its convergents. Let $x$ be some irrational number and let $p/q$ be one of its convergents. Then $p/q$ is the best rational approximation to $x$ for a denominator in the neigbourhood of $q$, with the error being $k/q^2$, where $k$ is a small integer ($k$ can often be 1). In contrast, if $p/q$ is not a convergent, we expect the error to be of the order of $k/q$.

To find the continued fraction representation of $\sqrt2$, we can proceed as follows.

Let $x = \sqrt2$
Then \begin{align} x^2-1 & = 1\\ (x+1)(x-1) & = 1\\ x-1 & = \frac{1}{1+x}\\ x & = 1 + \frac{1}{1+x}\\ \end{align}

We can now substitute that fraction for $x$ into itself:

$$x = 1 + \frac{1}{1+1 + \frac{1}{1+x}}$$ $$x = 1 + \frac{1}{2 + \frac{1}{1+x}}$$

And of course we can repeat the process:

$$x = 1 + \frac{1}{2 + \frac{1}{2+\frac{1}{2 + \frac{1}{1+x}}}}$$

If we continue this process indefinitely the 2s will keep repeating. The compact way to write this is $[1;2,2,2,…]$.

To obtain the convergents we evaluate the continued fraction from the beginning, ignoring subsequent terms. This gives us

$$\frac{1}{1}, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378}, \dots$$

You should be able to see a simple pattern in the numerators & denominators. Let's make that pattern explicit. We know that if $x = \sqrt 2$ then

\begin{align} x = 1 + \frac{1}{1+x}\\ x = \frac{x+2}{x+1} \end{align}

Now let $x = p/q$ be a rational approximation to $\sqrt 2$ and let $p'/q'$ be the next approximation. \begin{align} \frac{p'}{q'} = \frac{\frac{p}{q}+2}{\frac{p}{q}+1}\\ \frac{p'}{q'} = \frac{p+2q}{p+q} \end{align} Thus $p' = p+2q$ and $q' = p+q$


We can make this a little more rigorous. $\left(\frac{p}{q}\right)^2 \approx 2$, and in fact for the convergents shown earlier, $p^2 - 2q^2 = \pm 1$, hence $$\left(\frac{p}{q}\right)^2 = 2 \pm \frac{1}{q^2}$$

Let $p' = p+2q$ and $q' = p+q$
Then \begin{align} p'^2 - 2q'^2 & = (p+2q)^2 - 2(p+q)^2\\ & = p^2 + 4pq + 4q^2 - 2p^2 - 4pq - 2q^2\\ & = -p^2 + 2q^2 = -(p^2 - 2q^2)\\ p'^2 - 2q'^2 & = \mp 1 \end{align}

So if $\frac{p}{q}$ is a good approximation to $\sqrt 2$ then $\frac{p'}{q'}$ is also a good approximation to $\sqrt 2$, and it's a better one than $\frac{p}{q}$ because $q' > q$. (This is essentially a proof by induction).


We can factorize $p^2 - 2q^2 = (p + \sqrt 2 q)(p - \sqrt 2 q) = \pm 1$

Substituting $p=1, q=1$ from our first convergent, we get $$(1 + \sqrt 2)(1 - \sqrt 2) = -1$$

Raising both sides to the power of $n$: $$(1 + \sqrt 2)^n(1 - \sqrt 2)^n = (-1)^n$$

Now $$(p + \sqrt 2 q)(1 + \sqrt 2) = (p + 2q) + \sqrt 2(p + q) = p' + \sqrt 2 q'$$

So we can write $p_n + \sqrt 2 q_n = (1 + \sqrt 2)^n$, where each integer $n \ge 1$ gives us a convergent $\frac{p_n}{q_n}$. If we let $n$ take on successive powers of 2 then we get the approximations found by the Babylonian method.

$$p_{2i} + \sqrt 2 q_{2i} = (p_i + \sqrt 2 q_i)^2\\ = (p_i^2 + 2q_i^2) + \sqrt 2 2 p_i q_i$$

I'll also mention without proof that $p_{i+2} = 2p_{i+1} + p_i$ and $q_{i+2} = 2q_{i+1} + q_i$. Note that $p_i$ is always odd, and when $i$ is odd, so is $q_i$. Let $p = 2a + 1$. When $q$ is odd, $a^2+(a+1)^2=q^2$; when $q$ is even, $a^2+(a+1)^2=q^2+1$.


FWIW, here's a short Python script that calculates and tests these convergents. (This code runs on both Python 2 and Python 3).

from __future__ import print_function, division

p, q = 1, 1
print(' i:     p     q -> x   x*x')
fmt = '{0:2}: {1:5} {2:5} -> {3} {4}'
for i in range(1, 14):
    x = p / q
    print(fmt.format(i, p, q, x, x * x))
    p, q = p + 2 * q, p + q

output

 i:     p     q -> x   x*x
 1:     1     1 -> 1.0 1.0
 2:     3     2 -> 1.5 2.25
 3:     7     5 -> 1.4 1.96
 4:    17    12 -> 1.41666666667 2.00694444444
 5:    41    29 -> 1.41379310345 1.99881093936
 6:    99    70 -> 1.41428571429 2.00020408163
 7:   239   169 -> 1.41420118343 1.99996498722
 8:   577   408 -> 1.41421568627 2.0000060073
 9:  1393   985 -> 1.41421319797 1.99999896931
10:  3363  2378 -> 1.41421362489 2.00000017684
11:  8119  5741 -> 1.41421355165 1.99999996966
12: 19601 13860 -> 1.41421356421 2.00000000521
13: 47321 33461 -> 1.41421356206 1.99999999911


Finally, here's some code that uses (big) integer arithmetic and the Babylonian method to produce the decimal digits of $\sqrt 2$.

x = t = 1
for n in range(15):
    s = 10 * t
    x = 5 * x + (t * s) // x
    t = s
    print(x, x*x, (x+1)**2)   

output

15 225 256
141 19881 20164
1414 1999396 2002225
14142 199996164 200024449
141421 19999899241 20000182084
1414213 1999998409369 2000001237796
14142135 199999982358225 200000010642496
141421356 19999999932878736 20000000215721449
1414213562 1999999998944727844 2000000001773154969
14142135623 199999999979325598129 200000000007609869376
141421356237 19999999999912458800169 20000000000195301512644
1414213562373 1999999999999731161391129 2000000000002559588515876
14142135623730 199999999999973116139112900 200000000000001400410360361
141421356237309 19999999999999857198323561481 20000000000000140041036036100
1414213562373095 1999999999999999861967979879025 2000000000000002690395104625216
$\endgroup$
2
$\begingroup$

Other answers give efficient ways of finding additional terms of the Cauchy sequence, or sequences that may be better than the Cauchy series for practical purposes.

But as far as I'm concerned, the Cauchy sequence has nothing to do with practical computations. It is simply either a way of defining the real numbers or (if you prefer Dedekind cuts as a definition) a way of justifying infinite decimal representations of real numbers.

The Cauchy sequences $1, 1.4, 1.41, 1.414, 1.4142,\ldots$ and $2, 1.5, 1.42, 1.415, 1.4143, \ldots$ are well defined because after each step you have narrowed down the possible values of $\sqrt2$ to an interval of width $10^{-n}$ for some integer $n,$ and for the next step you say which of the $10$ equal subdivisions of that interval contains $\sqrt2.$

Since the point here is simply that there is an answer, not that we know how to find it quickly, you can appeal to "brute force." For example, after the upper and lower Cauchy sequences around $\sqrt2$ reach the terms $1.414$ and $1.415,$ respectively, the next term in each sequence has to come from the following set:

$$\{1.4140, 1.4141, 1.4142, 1.4143, 1.4144, 1.4145, 1.4146, 1.4147, 1.4148, 1.4149, 1.4150\}.$$

It takes only a finite number of steps to square all of these values and find out which ones are less than $\sqrt2$ and which are greater. (You already know two of the squares, so you only have to compute the other nine.) Once you have done this, you find that $1.4142^2 < 2 < 1.4143^2,$ so $\sqrt2$ is between $1.4142$ and $1.4143,$ which are therefore the next terms in the lower and upper sequences, respectively.

All the rest is optimization of the computations.

$\endgroup$
  • $\begingroup$ A simple PARI implementation with $a$ the lower sequence and $b$ the upper sequence may be: a=1; b=2; step=1.0; print(a," ",b); for (n=0,10,step=step/10;b=a+step;while(b^2<2,a=b;b=b+step);print(a, " ",b)) $\endgroup$ – Jaume Oliver Lafont May 30 '17 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.