Fibonacci Sequence

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.

It works for all x. Proof to follow...

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.

Indeed so. And yet there is an exception for which the sequence does *not* converge to the golden ratio of approx 1.618. *grins*

My proof has a few holes, but my guess (without proof) is that the relevant one is x = 1-p.

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.

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