Simple Number Pair Series Yields Surprising Ratio ... Why?

Date: 12/31/2009 at 11:28:56
From: John
Subject: Square root of two

Look at a series of pairs of numbers

   (a, b)
   (c, d)
   (e, f)
   
... such that

   c = a + b
   d = a + c
   e = c + d
   f = c + e

... and so on.
    
If you start with a = 0 and b = 1, the series runs ...

   (0, 1)
   (1, 1)
   (2, 3)
   (5, 7)
   (12, 17)
   (29, 41)
   (70, 99)

Now look at the ratio of the larger number in each ordered pair to the
smaller one. It gets ever closer to sqrt(2). For example, the 13th ordered
pair is (13860, 19601), and 19601/13860 = 1.41421356...., which is very
close to the square root of two.

For any seed n in (0, n), this ratio remains the same, with every number
in the series multiplied by n.

Can you explain in simple terms why this series converges on sqrt(2)?

I am not a mathematician. I studied maths at school up to age 16, but that
was about 50 years ago.

Thank you.

Date: 12/31/2009 at 20:08:12
From: Doctor Rick
Subject: Re: Square root of two

Hi, John.

What you've got here resembles the Fibonacci sequence:

  Golden ratio, Fibonacci sequence
    http://mathforum.org/dr.math/faq/faq.golden.ratio.html 

The ratio of consecutive Fibonacci numbers approaches the "golden ratio"
Phi = (1 + sqrt(5))/2. Using a method similar to the method commonly used
to show that result, we can show that your ratio approaches the square
root of 2.

If I call the nth element of your sequence (a[n], b[n]), the rules for
generating the pairs can be stated as follows:

  a[1] = 0, b[1] = 0
  a[n] = a[n - 1] + b[n - 1]
  b[n] = a[n - 1] + a[n]

The latter can be worked a little:

  b[n] = a[n - 1] + a[n - 1] + b[n - 1]
       = 2*a[n - 1] + b[n - 1]

The ratio of the two numbers in the nth pair can be evaluated as:

               2*a[n - 1] + b[n - 1]                a[n - 1]
  b[n]/a[n] = ----------------------- =   1 + ---------------------
                a[n - 1] + b[n - 1]            a[n - 1] + b[n - 1]

                           1
            = 1 + -----------------------
                   1 + b[n - 1]/a[n - 1]

Let's call that ratio x[n]:

  x[n] = b[n]/a[n]

Now we can reduce everything to a single recursion relation:

  x[n] = 1 + 1/(1 + x[n - 1])

If x[n] approaches a limit as n increases, then x[n - 1] will become
closer and closer to x[n - 1], so that the limit will be a value X such
that

  X = 1 + 1/(1 + X)

Now it's just a matter of solving this equation:

           X - 1 = 1/(1 + X)
  (X - 1)(1 + X) = 1
         X^2 - 1 = 1
             X^2 = 2

Thus, *if* x[n] has a limit, it must be either sqrt(2) or -sqrt(2).
Obviously, since a[n] and b[n] are always positive, the limit must be
positive.

I still haven't proved that there *is* a limit, but I think you're most
interested in what the limit is, so I'll skip that part unless you're
really interested.

The fact is, your ratio does approach exactly the square root of 2 as n
increases.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 04/02/2010 at 10:58:36
From: John
Subject: Thank you (Square root of two)

Thank you for most interesting reply.

I've been trying to find a similar series that converges on sqrt(3), but
so far, no success.

Thank you once again.