# Fibonacci Sequence

talzamir
Posers and Puzzles 26 Sep '11 22:08
1. 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. Anthem
The Ferocious Camel
26 Sep '11 23:01
It works for all x. Proof to follow...
3. 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. talzamir
Art, not a Toil
27 Sep '11 06:391 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. 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. 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. 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