3

I'm pretty sure we're all familiar with the Fibonacci sequence. Most people with more than passing knowledge of this most marvelous gem are aware of the Binet formula, $Fib(n) = (\varphi^n - (-\varphi)^n)/\sqrt{5}$. Unfortunately, this doesn't allow me to take, for example, $Fib(5.5) = 16.5$ or something like it, because it would involve taking the square root of a negative number.

I've tried using Excel to plot the graph, but it ends up being a poor approximation for moderately large (30) values of n, and I doubt its accuracy anyway, since taking different ranges from which to compute constants $k_1$ and $k_2$ in the formula $Fib(n) = k_1 * e^{k_2n}$ results in wildly different constants and varying degrees of accuracy.

How can I find the appropriate intermediate values for $Fib(n)$ for non-integer values of $n$? And in the event that I'm asking this wrong (for example, someone might say non-integer values of $Fib(n)$ is nonsensical) then I would kindly request your assistance in phrasing it properly - namely, if I were to plot the Fibonacci numbers on a Cartesian graph, and added a trendline that calculated them all perfectly, how could I acquire the values on the trendline between plot points?

corsiKa
  • 586
  • You seem to be looking for some kind of interpolation. – Git Gud May 16 '14 at 17:27
  • That sounds like an accurate description - but not only interpolation, but one that stays accurate via extrapolation as well. – corsiKa May 16 '14 at 17:38
  • 2
    Did you consider the analytic function $f$ defined on $[0,\infty)$ by $$f(x)=\frac{\varphi^x - \cos(x \pi)\varphi^{-x}}{\sqrt{5}} $$ (cf. http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Extension_to_all_real_or_complex_numbers ) ? – Clement C. May 16 '14 at 17:41
  • I hadn't, but taking $\varphi^{-x}$ seems like it would have the same "negative square root" problem I currently face. – corsiKa May 16 '14 at 17:44
  • 1
    @corsiKa How would that be a problem? $\varphi$ is a positive real number, so $\varphi^{-x}$ is a well-defined positive real number. –  May 16 '14 at 17:47
  • @corsiKa: Why? Here, $\varphi$ is the golden ratio, and thus is positive; and $\varphi^{-x}=1/\varphi^x$, which is well-defined for any positive real $x$. – Clement C. May 16 '14 at 17:48
  • Oi, I keep getting all my Phis mixed up with my phis... it causes me a lot of sighs... – corsiKa May 16 '14 at 17:49
  • @ClementC. That works perfectly! I can't believe the term "real" never popped into my head to search for... that is the first result for "fibonacci numbers for real numbers" ... Argh! – corsiKa May 16 '14 at 17:55

2 Answers2

8

You might be interested in the earlier question here in MSE ; there is a real good discussion concerning the whereabouts of the Binet-formula versus that formula for real values where S. Levenstein gave hints (and worked-out infos) for some background properties of that computation-methods. Also I'd just added two pictures for the interpolation of the Fibonaccis in the complex plane; I think it is best you look at that thread; but since the pictures are uploaded anyway I can refer to them here too: (I've just copied the text of my own update)

Just for the intuition: here is a picture which shows the curve in the complex plane for fibonacci-numbers due to the Binet-formula for fractional (but strictly real) indexes. To avoid the overlap of $\text{fib}(1)=\text{fib}(2)=1$ I used a slightly shifted version for the fibonacci-numbers, by setting $\text{fib}^*(0)=0.1, \text{fib}^*(1)=1.1$ and let the curve begin at index $-4$ :
The picture:

and the detail of a self-overlapping segment of the curve here

(The "real-only" version using the cos()-cofactor in the formula would give simply the straight line on the x-axis itself, but with back-an-forth-movements for the negative indexes.)

Community
  • 1
Gottfried Helms
  • 34,920
7

You can actually use the formula $\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}$ where $\varphi = \frac{1 + \sqrt{5}}{2}$. But for all non integer values you get complex numbers. These numbers are of the form $a + bi$ where a and b are the numbers you're famillar with, and $i$ is a constant defined as $i^2 = -1$ or equivalently $i = \sqrt{-1}$.

You can plot this function:
When you look at the plot, you can see the red line which is the imaginary part of the number, and the imaginary part is zero at all of the integer values, which makes sense since the fibonacci numbers aren't imaginary.

Edit: You can avoid complex numbers by using another formula. $$\frac{\varphi^x - \cos(\pi x)\varphi^{-x}}{\sqrt{5}}$$ When you plot this function, you get:

Alice Ryhl
  • 7,853