Interpolated Fibonacci numbers - real or complex?

Question

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.

Now in the mathworld-article there is no further reasoning about this and so I thought I ask here:

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

Answer 1

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.

Answer 2

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.

Answer 3

Just a side note to the perfect explanation above. For quick and dirty use, you can approximate Fibonacci sequence for $N > 4$ just with $$ 0.447215 \;e^{0.481212 \; x} $$ It has $R^2 \simeq 1$, so you won't lose much here.