Fibonacci Fantasy Copyright © 2000 by Paul Niquette. All rights reserved.
 Given that... 86,267,571,272 ...is a Fibonacci number. What is the next number in sequence? he 'recursion formula' for the Fibonacci series...
f(n+1) = fn + f(n-1)
...uses the values of the previous two numbers to produce the next. We have been given only that...
fn = 86,267,571,272
What's the matter? Did you forget the value of f(n-1)?

You can start over at 0, 1, 1, 2, 3, ..., 86,267,571,272, but that will take quite awhile. You may be pleased to know there's another way. n the mid-eighteenth century, Robert Simson at the University of Glasgow discovered that the ratio of two successive Fibonacci numbers 'tends' toward a constant. Figuring this out might have kept an old-time mathematician off the streets for weeks. For the sophisticated solver, the derivation is elementary.

With a modern calculator, one can effortlessly reconfirm Simson's discovery in seconds.

Care to try? Take any Fibonacci number and divide it by the next number in the series. Use 21 and 34, for example. You get 0.61764705. Or take the next pair, 34 and 55, which produces the ratio 0.618181818...

By the 29th and 30th number, you will see that the ratio has settled down -- 'converged,' in math-talk -- so that one can perceive no change in its value even with many digits of precision. The ratio approaches the constant value of...

 0.61803398874989484820...
Congratulations, you have found the value of something called (phi, usually pronounce FAE), which is a Greek letter, like (pi, usually pronounced PAE), commonly used to denote the ratio of a circle's circumference to its diameter, and 's value, 3.14159..., thanks to computers, has grown in precision to over 10 million decimal places. Likewise, also represents a ratio and is often called the "Golden Mean" or, in geometric form, "Golden Section."
For large Fibonacci numbers, therefore, the following formula applies: fn / f(n+1), so then...
f(n+1)  fn , and for the puzzle at hand...
f(n+1) 86,267,571,272 / 0.61803398874989484820...
 139,583,862,445
If you are empirically inclined, you might also enjoy confirming this solution with a spreadsheet and carrying out a few experiments to explore other properties of the Fibonacci Fantasy.

Derivation of Simson's Discovery

The (n + 1)st Fibonacci number is derived from the previous two as follows:

f(n+1) = fn + f(n-1)
which may be rearranged algebraically to read...
f(n-1)  /  ff(n+1)fn  - 1

Now, for Robert Simson's assertion to hold, as n approaches infinity (What an oxymoron! -- "approaching" that which cannot be approached?), the ratio of each Fibonacci number to its successor is a constant. Thus,...

f(n-1) / fn approaches fn / f(n+1)
Let's make it easy on ourselves by setting both ratios equal to and rewriting... =  1/ - 1. 2+ - 1 = 0
...has the solution... = (51/2 - 1) / 2 = 0.618033988750. y the way, mathematicians have classified along with as an "irrational number," which seems like an irrational choice of words, for the case at hand, inasmuch as irrational numbers -- by definition -- cannot result from the ratio of whole integers, which is exactly what each Fibonacci number happens to be.

The key to this paradox hides within that infinity business in the derivation provided above.

 Where parallel lines meet, so too do the rational and the irrational. -- Paul Niquette, 1997

{Return}

The sophisticated solver knows how to use a spreadsheet to create an interactive 'model' of a problem.

• columns designated by letters A, B,...
• rows designated by numbers 1, 2...
• fixed references are denoted by \$
• arithmetic operators +, -, *, /, sqrt(radicand)
Producing the Fibonacci Sequence is simplicity itself. Using column A, set...
A1 = 0 ~~ first number of the series f1
A2 = 1 ~~ second number of the series f2
A3 = A1 + A2 ~~ the Fibonacci Recursion Formula
A4 = A2 + A2 ~~ pasted entries with relative references
...
An = A(n-2) + A(n-1) ~~ for any size of table (let n = 50, say).
As noted in the puzzle, the 41st entry is indeed greater than 100 million (A41 = 102,334,155, to be exact).

To test Simson's Ratio, set...

B2 = A3 / A2 ~~ ratio of  f2 / f3
B3 = A4 / A3 ~~ pasted entries with relative references
...
Bn = A(n+1) / An ~~ ratio fn / f(n+1)
You will see that B19 = 0.618033963, which is a good approximation of . How good? Well you might place the formula for in the table (at C1 say)... = (51/2 - 1) / 2
C1 = (SQRT(5) - 1) / 2
...and compare in column Cn each value in Bn with the content of C\$1 (the \$ assures that the row number stays fixed in the comparisons throughout the series), as follows:
Cn = (C\$1 - Bn) / C\$1
If you do so, you will see that by the 18th Fibonacci number the empirical ratio agrees with the theoretical ratio by better than one part in 10 million. Exclamation point optional.
Now, what happens if we change the beginning numbers in A1 and A2? or no good reason, let's postulate a new family of Fibonacci numbers, using exactly the same recursive procedure, but started with different -- what shall we call them? -- "seeds." Try commencing your series with a couple of numbers that did not arise on the previous list, such as 4 and 7.
Watch the entries grow: 11, 18, 29, 47,... Take out your calculator and figure those ratios of succeeding values -- or scan your spreadsheet. They tend to the same value, 0.618033988750! That Golden Section turns up again.
Experimentation with any number of seed numbers always shows that outcome. Consider, too, the series started by 100 and 2. Notice how fast the numbers grow. The 34th exceeds the population of the U.S.; the 40th, the population of the world. Yet, those ratios steadfastly approach the same value .
You can plant a negative seed like -123 alongside, say, 77. After some vacillation, plus and minus, the numbers come out positive and sail off to infinity -- at Simson's fixed ratio still. Another amazement: By changing the 77 to 76, the consequent Fibonacci numbers stumble into a black hole of unlimited negativity -- but the ratio still holds. No exclamation point, please.
Why should we be surprised? Going back to Simson's ratio, we see that the only requirement for the analytically derived outcome is that the successive Fibonacci numbers must be large -- large enough to make the formula work, that is. Thus do we see the power of closed form analysis over empirical experimentation. Go ahead and put an exclamation point at the end of that sentence. {Return} 