# Interpolated Fibonacci numbers - real or complex?

The common Binet-formula for the Fibonacci-numbers $$f_n = {\varphi^n- (1-\varphi)^n \over \sqrt 5 } \small {\qquad \qquad \text{ where }\varphi={1+\sqrt 5\over 2}}$$

allows interpolation to negative and fractional indexes, however for non-natural indexes we have in general complex values (and also we lose uniqueness due to fractional powers of a negative basis). This is the interpolation-scheme which I'm used to.

In the mathworld-article on Fibonacci-numbers I found now the formula for the interpolation to noninteger indexes as $$f^*_x = {\varphi^x-\cos(\pi x) \varphi^{-x} \over \sqrt 5 }$$ which guarantees real values also for the interpolated fibonacci-numbers. While I like the idea to find some real-number-interpolation for the index which leads also to real numbers in the range, it still looks a bit ugly because of asymmetry and feels a bit like handwaving; compare the discussion about which is the best interpolation for the factorial and why we choose the Euler-gamma-function for this.... : one argument which made me confident that the Binet-interpolation is "the correct one" is similar to the same (possible) argument for the Euler's-gammafunction: it coincides also with the concept of indefinite summation, extended to fractional and even complex summation-indexes.

Q: is there any other reason for this type of interpolation other than the non-imaginary-ness of the resulting values for real indexes?
(an instructive reference were as well welcome...)

[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$ :
:

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

(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.)

• One way to look at the complex Binet formula is to look at the ratio, $r(z) = \frac{f_{z+1}}{f_z}$. With a bit of algebra, $r(z+1)=1+1/r(z)$. The ratio has two fixed points, $\phi$, and $1-\phi$. The ratio equation in the complex plane is a solution to the inverse Schroder equation, developed via a "regular superfunction". One can also look at the ratio for the real valued fibonacci solution, which behaves asymptotically like r(z) as $\Im(z) \to -\Im \infty$, and assymptotically like conj(r(conj(z))) as $\Im(z) \to +\Im \infty$. But this is probably unnecessarily complicated..... – Sheldon L Dec 3 '13 at 15:06
• Hi @Sheldon - I think that's exactly what one would intuitively do with the method of iteration by powers of the associated matrix: the eigenvalues are just the values in the nominator of the Binet-formula, and the matrix-powers coincide with the Binet's powers. Thus I "trust" this method more, because it coincides with the "superfunction"-concept (the eigenmatrices provide the Schröder-function and its inverse and so on...) – Gottfried Helms Dec 3 '13 at 15:11
• It turns out that the ratio function for the complex Binet formula is related to the ratio for the real valued solution, in exactly the same way as the complex solution for tetration is to the kneser real valued solution for tetration :) But I think this is an unnecessarily complicated view of the real valued fibnoacci solution. My computer at home is making some pictures, which I may post later.... – Sheldon L Dec 3 '13 at 15:27
• @Sheldon - perhaps this is related: go.helms-net.de/math/tetdocs/FracIterAltGeom.htm because of your reference to iteration of $1/(1+x)$ or, $r(z+1) = 1/(1+r(z))$ – Gottfried Helms Dec 3 '13 at 17:20
• yes, the ratio function should be the same solution as in your document. – Sheldon L Dec 3 '13 at 20:24

I like the "talk" section of wikipedia, Talk:Generalizations_of_Fibonacci_numbers. I am quoting from their writeup.

According to Binet's formula,

$$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$$

Since $\psi = -\frac{1}{\varphi}$, this formula can also be written as

$$F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}$$

Now if you factor the $-1$ out of the $-\varphi$, you get

$$F_n = \frac{\varphi^n-(-1)^{-n}\varphi^{-n}}{\sqrt 5}$$ ... And from Euler's identity, $-1 = e^{i\pi}$, so

$$F_n = \frac{\varphi^n-e^{i\pi n}\varphi^{-n}}{\sqrt 5}$$

Ok, now continuing on my own.... And from Euler's formula, $e^{i\pi n} = \cos (\pi n) + i \sin (\pi n)$, so Binet's solution can be equivalently expressed as $F_1$, to distinguish it from its complex conjugate.

$$F_1(z) = \frac{\varphi^z-(\cos (\pi z) + i \sin (\pi z))\varphi^{-z}}{\sqrt 5}$$

There is an alternative definition, with $-1 = e^{-i\pi}$, which leads to the complex conjugate solution, which I will label $F_2$.

$$F_2(z) = \frac{\varphi^z-(\cos (\pi z) - i \sin (\pi z))\varphi^{-z}}{\sqrt 5}$$

Due to the fact that linear combinations of solutions to the Fibonacci recurrence relation are also solutions, we can average $F_1$ and $F_2$ together, and get the real valued solution, $F_{\text{real}}(z)$, where at the real axis, the imaginary term cancels with its conjugate.

$$F_\text{real}(z) = \frac{F_1(z)+F_2(z)}{2} = \frac{\varphi^z-\cos (\pi z) \varphi^{-z}}{\sqrt 5}$$

I think both solutions are equally valid, and perhaps sometimes it seems more natural to have a real valued solution, and this derivation shows where the "cos" term in that solution comes from. As I noted in earlier comments, there is also some interesting behavior for the "ratio" function for these various solutions, $r(z)=\frac{F(z+1)}{F(z)}$, which I may post later, which connects the complex solution to the formal Schroeder function solution for the ratio function.

• Hi Sheldon, thanks for the link. Yes, well, I've seen that method expressed in a similar way in - I think - mathworld. But I didn't see more than just the comment, that the result of the operation leads to real numbers - and my question is, whether there is more than that simple functionality. (That the question of (non-) uniqueness of the method of interpolation and its final choice is nontrivial can be seen by the sometimes re-initiated question of the right choice of the interpolation of the factorial function to the version of L. Euler. – Gottfried Helms Dec 4 '13 at 8:58
• A discussion about the sum of logarithms of consecutive integers lead, via the indefinite sum-argument, just to the formula for the $\ln\Gamma$, and re-discovered this way the Euler-version for the $\Gamma$ itself (this was an incidence-finding, it was not originally intended). See here go.helms-net.de/math/divers/BernoulliForLogSums.pdf – Gottfried Helms Dec 4 '13 at 9:08

This is for Gottfried, and anyone else interested in how a Kneser style tetration mapping is related to the real valued Fibonacci extension. Another completely different way of looking at these two Fibonacci functions, is to look at the ratio function,

$$r(z)=\frac{f(z+1)}{f(z)}$$

I have two conjectures, which I posted in comments earlier, that I will give numerical evidence for. 1) The Schroeder function from the fixed point $r\mapsto 1+1/r$, leads to a solution for the iterated function $r^z$, which, with a constant, is the same as Binet's formula for the Fibonacci function. 2) A kneser mapping of $r^z$ leads to the alternative real valued Fibonacci solution.

The ratio function has two fixed points, $\varphi$ and $1-\varphi$, which can be derived as follows:

$$r(z+1)=\frac{f(z+2)}{f(z+1)}=\frac{f(z+1)+f(z)}{f(z+1)}=1+\frac{f(z)}{f(z+1)}$$ $$r(z+1)=1+\frac{1}{r(z)}$$

So, now we see that r(z) is itself an iterated function, which can be solved for its fixed points, where $r(z+1)=r(z)$ if $r(z)=\varphi$ or if $r(z)=1-\varphi$. These fixed points can be found by solving the quadratic equation, $x^2-x-1=0$, whose roots are $\frac{1 \pm\sqrt{5}}{2}$.

So, now that we have r(z) and its fixed points, it is natural to consider the Schroeder function, $S(z)$ and the inverse of the Schroeder function $S^{-1}(z)$, for r(z). I developed the Schroeder function around the repelling fixed point, $1-\varphi$. We shift the fixed point to the vicinity of zero, by defining the substitution $z=y+1-\varphi$, and definining $r_y(y+1)=\frac{\varphi r(y)}{r(y)-\varphi+1}$, and then we have $r_y(y+1) \approx -(\varphi+1)r_y(y)$. So we define $\lambda=-(\varphi+1)$, and then develop the Schroeder function and its inverse, both the Schroeder function and its inverse turn out to have surprisingly simple closed forms.

$$S(r_y o z) = \lambda S(z)$$ $$S(z)= 1 + 5^{-0.5}z + 5^{-1}z^2 + 5^{-1.5}z^3 + 5^{-2}z^4 + 5^{-2.5}z^5 +...$$ $$S^{-1}(z)= 1 - 5^{-0.5}z + 5^{-1}z^2 - 5^{-1.5}z^3 + 5^{-2}z^4 - 5^{-2.5}z^5 +...$$

One can now generate the Abel function, and its inverse, which have the same iterated function definition as the ratio function, $r(z)$. The Abel function is the inverse of the ratio function, where $\alpha(z)$ generated from the Schroeder function is $\alpha(z) = \log_\lambda(S(z+\varphi-1))$. One can also define the inverse Abel function, which has exactly the same iterated definition as the ratio function $r(z)$. $$\alpha^{-1}(z) = S^{-1}(\lambda^z)+1-\varphi$$

So, what happens if we take the $\alpha \circ r(z)$, where $r(z)$ is generated from the Binet formula? Numerically, the answer is z + a simple constant. I'm not sure how to prove the result (I have many ideas, but not nearly enough time right now). This is the first half of my conjecture.

$\alpha(r(z)) = z + k$ where k is a constant, $k \approx 0.985941029676055376744 + 0.0458920121936640893630i$. This leads to the following equivalent alternative definition for the ratio function, developed from the Binet solution. There are two choices for the $\pm\exp(\pi iz)$ term, and one has to choose the correct pairing, with the $\alpha$ function.

$$r(z) = \alpha^{-1}(z+k)$$ $$f(z) = \frac{\varphi^{z+1}}{\alpha^{-1}(z+k)\varphi+1} = \frac{\varphi^z-\exp(-\pi i z)\varphi^{-z}}{\sqrt{5}}$$

The last line gives a conjectured equivalent form for the Binet Fibonacci formula, in terms of the ratio function, developed from the Schroeder equation. The key piece of this work was to generate the Fibonacci function from the ratio function, $r(z)$. I used this formala, found online at Fibonacci formulae, and a little algebra ....
$$\varphi^n = f(n+1) + f(n)/\varphi$$ $$f(z) = \frac{\varphi^{z+1}}{(\varphi f(z+1)/f(z)+1)}$$ $$f(z) = \frac{\varphi^{z+1}}{(\varphi r(z)+1)}$$

I was able to get better than 60 decimal digits accuracy, using this equation. I got similarly accurate results for the second half of my conjecture, by taking the Abel function of the ratio function for the real valued Fibonacci function. The $\theta(z)$ mapping can be defined as follows, which leads to the Kneser $\theta$ mapping equation for the real valued version of f(z) from the Abel function. The coefficients for the theta(z) function are listed below. Of course it turns out $\theta(z)$ has a singularity at the real axis, so I generated and verified the 1-cyclic theta mapping via a Fourier transform at $\Im(z)=0.1i$ The singularity occurs where $r(z)=\varphi$, which occurs at z=n+0.5 for integers, where $\theta(z)$ goes to $-i\infty$. The $\theta(z)$ function has the same 1-cyclic form it has for a Kneser mapping used in calculating tetration, where $\theta(z)$ exponentially decays to a constant as $\Im(z)$ increases, and has a singularity at the real axis. $\theta(z)$ maps a complex valued ratio function from the Schroeder equation, into a real valued ratio function, which leads to a real valued Fibonacci function. I could post the pari-gp code I wrote for the Fibonacci problem.... The biggest obstacles are figuring out the correct logarithm for the abel function, and normal programming problems. There are some pretty graphs, I added below.

$$\alpha(r_{\text{real}}(z)) = z + \theta(z) = z + \sum_{n = 0}^{\infty} a_n\times \exp(2n\pi i z)$$ $$\theta(z) = \sum_{n = 0}^{\infty} a_n\times \exp(2n\pi i z) = \alpha(r_{\text{real}}(z)) -z$$ $$f_\text{real}(z) = \frac{\varphi^{z+1}}{\alpha^{-1}(z+\theta(z))\varphi+1} = \frac{\varphi^z-\cos(\pi z)\varphi^{-z}}{\sqrt{5}}$$ - Sheldon

Here are the first 100 coefficients of $\theta(z)$, printed accurate to approximately 28 decimal digits. I generated a 200 term series, and verified that the results matched the real valued Fibonacci definition, accurate to approximately 55 decimal digits.

a0=   1.04773332894435818689238486499 - 0.1558135811857976133389093993*I
a1=  -0.08914744371950718632557515378 + 0.2909996592881151279321051050*I
a2=   0.04457372185975359316278757689 - 0.1454998296440575639660525525*I
a3=  -0.02971581457316906210852505126 + 0.09699988642937170931070170167*I
a4=   0.02228686092987679658139378845 - 0.07274991482202878198302627625*I
a5=  -0.01782948874390143726511503076 + 0.05819993185762302558642102100*I
a6=   0.01485790728658453105426252563 - 0.04849994321468585465535085083*I
a7=  -0.01273534910278674090365359340 + 0.04157137989830216113315787214*I
a8=   0.01114343046493839829069689422 - 0.03637495741101439099151313812*I
a9=  -0.009905271524389687369508350420 + 0.03233329547645723643690056722*I
a10=  0.008914744371950718632557515378 - 0.02909996592881151279321051050*I
a11= -0.008104313065409744211415923071 + 0.02645451448073773890291864591*I
a12=  0.007428953643292265527131262815 - 0.02424997160734292732767542542*I
a13= -0.006857495670731322025044242599 + 0.02238458917600885599477731577*I
a14=  0.006367674551393370451826796699 - 0.02078568994915108056657893607*I
a15= -0.005943162914633812421705010252 + 0.01939997728587434186214034033*I
a16=  0.005571715232469199145348447111 - 0.01818747870550719549575656906*I
a17= -0.005243967277618069783857361987 + 0.01711762701694794870188853559*I
a18=  0.004952635762194843684754175210 - 0.01616664773822861821845028361*I
a19= -0.004691970722079325596082902831 + 0.01531577154147974357537395289*I
a20=  0.004457372185975359316278757689 - 0.01454998296440575639660525525*I
a21= -0.004245116367595580301217864466 + 0.01385712663276738704438595738*I
a22=  0.004052156532704872105707961536 - 0.01322725724036886945145932295*I
a23= -0.003875975813891616796764137121 + 0.01265215909948326643183065674*I
a24=  0.003714476821646132763565631408 - 0.01212498580367146366383771271*I
a25= -0.003565897748780287453023006151 + 0.01163998637152460511728420420*I
a26=  0.003428747835365661012522121299 - 0.01119229458800442799738865788*I
a27= -0.003301757174796562456502783473 + 0.01077776515881907881230018907*I
a28=  0.003183837275696685225913398349 - 0.01039284497457554028328946804*I
a29= -0.003074049783431282287088798406 + 0.01003447100993500441145190017*I
a30=  0.002971581457316906210852505126 - 0.009699988642937170931070170167*I
a31= -0.002875723990951844720179843670 + 0.009387085783487584772003390484*I
a32=  0.002785857616234599572674223556 - 0.009093739352753597747878284531*I
a33= -0.002701437688469914737138641024 + 0.008818171493579246300972881970*I
a34=  0.002621983638809034891928680994 - 0.008558813508473974350944267794*I
a35= -0.002547069820557348180730718679 + 0.008314275979660432226631574429*I
a36=  0.002476317881097421842377087605 - 0.008083323869114309109225141806*I
a37= -0.002409390370797491522312841994 + 0.007864855656435543998165002838*I
a38=  0.002345985361039662798041451415 - 0.007657885770739871787686976447*I
a39= -0.002285831890243774008348080866 + 0.007461529725336285331592438590*I
a40=  0.002228686092987679658139378845 - 0.007274991482202878198302627625*I
a41= -0.002174327895597736251843296434 + 0.007097552665563783608100124512*I
a42=  0.002122558183797790150608932233 - 0.006928563316383693522192978690*I
a43= -0.002073196365569934565711050088 + 0.006767433936932909951909421046*I
a44=  0.002026078266352436052853980768 - 0.006613628620184434725729661477*I
a45= -0.001981054304877937473901670084 + 0.006466659095291447287380113444*I
a46=  0.001937987906945808398382068560 - 0.006326079549741633215915328370*I
a47= -0.001896754121691642262246279868 + 0.006191482112513087828342661808*I
a48=  0.001857238410823066381782815704 - 0.006062492901835731831918856354*I
a49= -0.001819335586112391557664799057 + 0.005938768556900308733308267449*I
a50=  0.001782948874390143726511503076 - 0.005819993185762302558642102100*I
a51= -0.001747989092539356594619120662 + 0.005705875672315982900629511863*I
a52=  0.001714373917682830506261060650 - 0.005596147294002213998694328942*I
a53= -0.001682027239990701628784436864 + 0.005490559609209719394945379340*I
a54=  0.001650878587398281228251391737 - 0.005388882579409539406150094537*I
a55= -0.001620862613081948842283184614 + 0.005290902896147547780583729182*I
a56=  0.001591918637848342612956699175 - 0.005196422487287770141644734018*I
a57= -0.001563990240693108532027634277 + 0.005105257180493247858457984298*I
a58=  0.001537024891715641143544399203 - 0.005017235504967502205725950086*I
a59= -0.001510973622364528581789409386 + 0.004932197615052798778510256017*I
a60=  0.001485790728658453105426252563 - 0.004849994321468585465535085083*I
a61= -0.001461433503598478464353691046 + 0.004770486217837952916919755820*I
a62=  0.001437861995475922360089921835 - 0.004693542891743792386001695242*I
a63= -0.001415038789198526767072621489 + 0.004619042210922462348128652460*I
a64=  0.001392928808117299786337111778 - 0.004546869676376798873939142266*I
a65= -0.001371499134146264405008848520 + 0.004476917835201771198955463154*I
a66=  0.001350718844234957368569320512 - 0.004409085746789623150486440985*I
a67= -0.001330558861485181885456345579 + 0.004343278496837539222867240373*I
a68=  0.001310991819404517445964340497 - 0.004279406754236987175472133897*I
a69= -0.001291991937963872265588045707 + 0.004217386366494422143943552246*I
a70=  0.001273534910278674090365359340 - 0.004157137989830216113315787214*I
a71= -0.001255597798866298398951762729 + 0.004098586750536832787776128239*I
a72=  0.001238158940548710921188543803 - 0.004041661934557154554612570903*I
a73= -0.001221197859171331319528426764 + 0.003986296702576919560713768562*I
a74=  0.001204695185398745761156420997 - 0.003932427828217771999082501419*I
a75= -0.001188632582926762484341002050 + 0.003879995457174868372428068067*I
a76=  0.001172992680519831399020725708 - 0.003828942885369935893843488224*I
a77= -0.001157759009344249173059417582 + 0.003779216354391105557559806558*I
a78=  0.001142915945121887004174040433 - 0.003730764862668142665796219295*I
a79= -0.001128448654677306156019938655 + 0.003683539990988799087748165886*I
a80=  0.001114343046493839829069689422 - 0.003637495741101439099151313812*I
a81= -0.001100585724932187485500927824 + 0.003592588386273026270766729691*I
a82=  0.001087163947798868125921648217 - 0.003548776332781891804050062256*I
a83= -0.001074065586982014293079218720 + 0.003506019991423073830507290422*I
a84=  0.001061279091898895075304466116 - 0.003464281658191846761096489345*I
a85= -0.001048793455523613956771472397 + 0.003423525403389589740377707118*I
a86=  0.001036598182784967282855525044 - 0.003383716968466454975954710523*I
a87= -0.001024683261143760762362932802 + 0.003344823669978334803817300057*I
a88=  0.001013039133176218026426990384 - 0.003306814310092217362864830739*I
a89= -0.001001656671005698722759271391 + 0.003269659093124889077888821404*I
a90=  0.0009905271524389687369508350420 - 0.003233329547645723643690056722*I
a91= -0.0009796422386759031464348917997 + 0.003197798453715550856396759396*I
a92=  0.0009689939534729041991910342802 - 0.003163039774870816607957664185*I
a93= -0.0009585746636506149067266145568 + 0.003129028594495861590667796828*I
a94=  0.0009483770608458211311231399338 - 0.003095741056256543914171330904*I
a95= -0.0009383941444158651192165805661 + 0.003063154308295948715074790579*I
a96=  0.0009286192054115331908914078519 - 0.003031246450917865915959428177*I
a97= -0.0009190458115413111992327335441 + 0.002999996487506341525073248505*I
a98=  0.0009096677930561957788323995284 - 0.002969384278450154366654133724*I
a99= -0.0009004792294899715790462136746 + 0.002939390497859748766990960657*I
a100=  0.0008914744371950718632557515378 - 0.002909996592881151279321051050*I


This is the ratio function for the Binet solution. As imag(z) increases, or real(z) decreases, the ratio function goes to $1-\varphi$; as imag(z) decreases or real(z) increases, the ratio function goes to the other fixed point $\varphi$. There is a singularity for the ratio function at $z=0$, where Fib(z)=0. The ratio function is periodic, with $\text{period}=\frac{2\pi i}{\log(-\varphi-1)}$. The grid lines spacing is two units, with all of the graphs varying from 5+4i to -5-4i.

This is the ratio function for the real valued Fibonacci solution. As imag(z) increases, it quickly converges to the image above. There is a singularity for the ratio function at $z=0$, where Fib(z)=0. The ratio function is not as well behaved for z<0, at the real axis, with repeated simple poles, but it is reasonably well beahved for z>0 at the real axis as the real valued ratio function cycles towards $\varphi$. The function is pseudo periodic, with $\text{period}\approx\frac{2\pi i}{\log(-\varphi-1)}$, in the upper half of the complex plane. Since the function is real valued at the real axis, for $\Im(z)<0$, it goes to the conjugate function.

This is the Binet Fibonacci solution.

And here is the real valued Fibonacci solution, which looks like the Binet solution in the upper half of the complex plane, and the conjugate solution in the lower half of the complex plane; but only the ratio function has a rigorous 1-cyclic mapping.

• I added some pictures of the ratio functions and the Fibonacci functions. – Sheldon L Dec 7 '13 at 1:02
• This is a very nice discussion -thank you very much. And also the images give a nice and new overview for the functions. Really cool! – Gottfried Helms Dec 7 '13 at 9:38
• @SheldonL How did you produce those complex pictures? Please do tell! – zerosofthezeta Dec 7 '13 at 21:17
• @zeta, mike3 provided the original pari-gp code I used on the tetration forum, math.eretrandre.org/tetrationforum/showthread.php?tid=536 which I have used with modifications to make it run much faster (though still slow). It outputs ".ppm" "r,g,b" image files, which can then be changed into .png or .jpg files in an image editor. Pari-gp is the only math programming language I have, and its pretty slow at creating this kind of images, but, they are pretty! I think the definition is the same as this link. commons.wikimedia.org/wiki/User:Jan_Homann/Mathematics – Sheldon L Dec 7 '13 at 21:45