How is the sequence 1, 1.4, 1.41, 1.414 generated?

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, ...

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?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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)