Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member talzamir
    Art, not a Toil
    26 Sep '11 22:08
    The sequence is quite famous, but just in case. It starts with two one's and the rest of the numbers are sums of the two numbers preceding it. That is, the sequence starts with

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

    If you divide a number in the sequence with the one that precedes it the ratios converge to the golden ratio, approximately 1.618. Perhaps surprisingly, the same usually applies even if the second number in the series is tweaked. Say, start with 1 and -6 or 1 and 0, you get

    1, -6, -5, -11, -16, -27, -43, -70, ...
    1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

    again, the ratios converge to the golden ratio.

    The question is.. if you tweak the 2nd number in the Fibonacci sequence, getting

    1, x, x+1, 2x + 1, 3x + 2, 5x + 3 ...

    ...are there any values for x for which the sequences does NOT converge to the golden ratio? If not, why not; if yes, find such a value.
  2. Donation Anthem
    The Ferocious Camel
    26 Sep '11 23:01
    It works for all x. Proof to follow...
  3. Donation Anthem
    The Ferocious Camel
    26 Sep '11 23:19
    Okay. Letting fn be the nth fibonacci number, and F0 = 1, F1 = x, Fn = F(n-1) + F(n-2), we can easily show that Fn = f(n-1)x + f(n-2).

    So, F(n+1)/Fn = ((fn)x + f(n-1))/(f(n-1)x + f(n-2))
    = 1/((fn/f(n+1)) + 1/x - (fn/(f(n+1)))) + 1/(x + (f(n-1)/fn)) (less complicated looking on paper, remember that f(n-1) = f(n+1) - fn)

    as n --> inf, the last expression goes to something that simplifies to (using p to represent the golden ratio):

    p((px^2 +2x + p - 1)/(px^2 +(p^2 - p + 1)x + p - 1) (*)

    p^2 - p + 1 = p(p-1) + 1 = p/p + 1 = 2 (remember p - 1 = 1/p)

    Thus (*) = p.
  4. Standard member talzamir
    Art, not a Toil
    27 Sep '11 06:39 / 1 edit
    Indeed so. And yet there is an exception for which the sequence does *not* converge to the golden ratio of approx 1.618. *grins*
  5. Donation Anthem
    The Ferocious Camel
    28 Sep '11 01:10
    My proof has a few holes, but my guess (without proof) is that the relevant one is x = 1-p.
  6. Standard member talzamir
    Art, not a Toil
    28 Sep '11 07:50
    Indeed it is.

    My proof goes like this.

    Let a by a number in a Fibonacci sequence that has converged so that the ratio of consequent numbers does not change anymore, or never did. If the ratio is r, then the next number is ar and the one after that ar^2, but since it is a Fibonacci sequence, it is also a + ar. That gives the equation

    a + ar = ar^2

    a(r^2 - r - 1) = 0

    which is true for a = 0 (not relevant here, but starting a Fibonacci sequence with two zeros gives a really boring sequence of zeros only) and for r = (1 +/- sqrt(5))/2, that is, p and 1 - p, about 1.618 and -0.618. The latter is an unstable equilibrium, making a sequence where the ratio stays the same while the numbers approach zero, and if the values differ by even a trifling amount from 1 - p, the ratio converges to p instead. My computer valiantly makes it past about 50 iterations before it surrenders to the might of the golden ratio.
  7. Donation Anthem
    The Ferocious Camel
    29 Sep '11 22:21
    A second proof, by induction, highlighting the fact that the ratio remains the same, start to finish:

    F0 = 1, F1 = 1-p so F1/F0 = 1-p
    Fn+1/Fn = (Fn + Fn-1)/ Fn = 1 + Fn-1/Fn = (using induction) 1 + 1/(1-p) = 1 - p