A puzzle about a Fibonacci-like sequence

I’m thinking of a mathematical sequence, S, whose terms are all nonnegative real numbers. It is infinite in both directions. Like the Fibonacci sequence, it satisfies the relation:

\displaystyle S_n=S_{n-1}+S_{n-2}

And we are given:

\displaystyle S_0=1

What is the value of S_1? Surprisingly, you have enough information to figure it out.


Note that the relation above can be rewritten to let us calculate the earlier terms of the sequence: S_n=S_{n+2}-S_{n+1}. The double-ended Fibonacci sequence looks like this:

\displaystyle\dots, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, \dots

Although it’s not really important here, it’s interesting to extend the Fibonacci sequence to all the real numbers. The usual closed-form formula doesn’t work, because it would require us to take negative numbers to non-integer powers. But there are ways to do it, and the most sensible one seems to be the formula:

\displaystyle\frac{\varphi^x - \cos(x \pi)\varphi^{-x}}{\sqrt{5}}

Where \varphi is the golden ratio\frac{1+\sqrt{5}}{2}, or about 1.6180339887.

Back to the puzzle. The keys is that, as we extend the sequence to the left, it usually starts to oscillate between increasingly large positive and negative numbers. But I said the sequence contains no negative numbers. So, what values of S_1 would cause it not to oscillate?

Let’s try S_1=2 and see what happens. In this case we get the Fibonacci sequence, shifted slightly from its usual indices:

\displaystyle\dots, -8, 5, -3, 2, -1, 1, 0, 1, 1, \boxed{2}, 3, 5, 8, \dots

Here’s a graph of this (made with desmos.com), extended to all reals to make it prettier. Only the values at integers are actually relevant.

fibonaccilike1

If we try S_1=3, we get the Lucas numbers:

\displaystyle\dots, 7, -4, 3, -1, 2, 1, \boxed{3}, 4, 7, \dots

If we try S_1=1.5, we get a sequence where every term is one half of a Fibonacci number:

\displaystyle\dots, -4, 2.5, -1.5, 1, -0.5, 0.5, 0, 0.5, 0.5, 1, \boxed{1.5}, 2.5, 4, \dots

If we try S_1=1.6, it takes a little longer to reach negative terms:

\displaystyle\dots, -0.6, 0.4, -0.2, 0.2, 0.0, 0.2, 0.2, 0.4, 0.6, 1, \boxed{1.6}, \dots

Hmm…

In fact, almost every Fibonacci-like sequence has a “wobble” to it, and that wobble will tend to cause it to eventually cross the X axis and become negative. The only exception is if the ratio of some term to the previous term is exactly the golden ratio, \varphi. In that case, all the terms are the integer powers of the golden ratio (multiplied by some constant). The curve is then a simple exponential curve, which has no wobble, and never goes negative.

So that’s the answer. Since S_0 equals 1, S_1 must equal \varphi, the golden ratio. That’s the only value for which all the terms are positive. Extended to all reals, it looks like this:

fibonaccilike2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s