Tetration Forum

Full Version: fibonacci like
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2
i was thinking about a fibonacci like recursion.

f(x) = f(x - 1) + f(x + i)

together with some initial conditions ( you choose )

perhaps old hat ... but i dont recall a closed form solution ( though its really hot here )

regards

tommy1729
anyone ?
(07/10/2010, 12:27 PM)tommy1729 Wrote: [ -> ]f(x) = f(x - 1) + f(x + i)

i = imaginary unit?
(07/15/2010, 02:29 AM)bo198214 Wrote: [ -> ]
(07/10/2010, 12:27 PM)tommy1729 Wrote: [ -> ]f(x) = f(x - 1) + f(x + i)

i = imaginary unit?

if it is meant
f(x) = f(x - 1) + f(x + 1)

then with b = 1/2 *(1+sqrt(3)*I) // complex cuberoot of -1

f(x) = b^x

is one solution.

Gottfried
(07/15/2010, 02:29 AM)bo198214 Wrote: [ -> ]
(07/10/2010, 12:27 PM)tommy1729 Wrote: [ -> ]f(x) = f(x - 1) + f(x + i)

i = imaginary unit?

yes , i^2 = -1.
(07/15/2010, 12:06 PM)tommy1729 Wrote: [ -> ]
(07/15/2010, 02:29 AM)bo198214 Wrote: [ -> ]
(07/10/2010, 12:27 PM)tommy1729 Wrote: [ -> ]f(x) = f(x - 1) + f(x + i)

i = imaginary unit?

yes , i^2 = -1.

then its not a recursion, i.e. you dont have a unique solution for natural number arguments.
I dont think the usual methods apply.
(07/16/2010, 07:03 AM)bo198214 Wrote: [ -> ]
(07/15/2010, 12:06 PM)tommy1729 Wrote: [ -> ]
(07/15/2010, 02:29 AM)bo198214 Wrote: [ -> ]
(07/10/2010, 12:27 PM)tommy1729 Wrote: [ -> ]f(x) = f(x - 1) + f(x + i)

i = imaginary unit?

yes , i^2 = -1.

then its not a recursion, i.e. you dont have a unique solution for natural number arguments.
I dont think the usual methods apply.

i didnt claim unique solutions.

the usual method relates such equations with polynomials ;

f(x+a) is associated with x^a , but since x - x^-1 - x^i isnt a polynomial , its trivially not solvable by the usual methods , at least not the usual methods " alone ".

if it was solvable by the usual method , i would have done so and would not have posted it here.

why isnt it a recursion ???

im looking for solutions that are analytic almost everywhere.

tommy1729
Hmm. We have

\( f(z) = f(z - 1) + f(z + i) \)

If we assume a solution of the form \( f(z) = r^z \) exists, like in the Fibonacci numbers, we can get the equation

\( r^z = r^{z-1} + r^{z+i} \)

Dividing both sides by \( r^{z-1} \) gives

\( r = 1 + r^{1+i} \)

or

\( r^{1+i} - r = -1 \).

There is a caveat, however: \( r^{1+i} \) is multivalued. It is more useful, then, to recast this equation in terms of \( u = \log( r ) \),

\( e^{(1+i)u} - e^u = -1 \)

and then the solutions for the functional equation are given by \( f(z) = e^{uz} \) for any \( u \)-value satisfying the above exponential equation. The functional equation is linear, so any linear combination of such solutions will be another solution, and since there are infinitely many such \( u \)-values, we can even consider infinite sums

\( f(z) = \sum_{n=0}^{\infty} C_n e^{u_n z} \)

with arbitrary \( C_n \), provided this sum converges. Since there are infinitely many constants \( C_n \), one could say the equation is like it has "infinitely many initial conditions".

This graph shows the function \( e^{(1+i)u} - e^u + 1 \) on the complex plane. You can see the roots, the values of \( u \) used to construct solutions of the functional equation. The scale runs between \( \pm30 \) on each axis (x = real, y = imag). One set of roots seems to lie along the line \( t + it \), while the other seems to lie along a slight curve (curving not visible here) that is asymptotic to the imaginary axis \( it \).

[attachment=717]

For example, we could take two terms with the roots given by \( u_0 \approx 0.5397851608092811048455891598 + 0.5397851608092811048455891598i \) and \( u_1 \approx -1.453673666461041618684343568 - 1.453673666461041618684343568i \) and coefficients \( C_0 = C_1 = 1 \). This function is plotted below at the same scale. Numerical calculation can be done to verify it really does solve \( f(z) = f(z-1) + f(z+i) \). I do not believe there is a closed form solution for these \( u \)-values in terms of any conventional special functions, but I could be wrong (and if I am, I'd like to know what the closed solution is.).

[attachment=718]

Note that these may not be the only possible solutions -- remember that the very simple case \( f(z) = f(z-1) \) has all 1-periodic functions as solutions. Not sure what the appropriate analogy is here. But the above could be thought of as a sort of "canonical" solution like how Binet's formula solves the Fibonacci numbers.
(07/17/2010, 01:50 AM)mike3 Wrote: [ -> ]...

Very nice!

I had tried it up to
Quote:\( e^{(1+i)u} - e^u = -1 \)
but gave up then...

Gottfried
(07/17/2010, 07:02 AM)Gottfried Wrote: [ -> ]
(07/17/2010, 01:50 AM)mike3 Wrote: [ -> ]...

Very nice!

I had tried it up to
Quote:\( e^{(1+i)u} - e^u = -1 \)
but gave up then...

What's the problem? This is just from setting \( r = e^u \) or \( u = \log( r ) \), since the \( \log \) needed to raise to the complex exponent is multivalued. I do not think it can be solved in closed form. The values tested were obtained by numerical root-finding methods (Newton's method, specifically). There could be some kind of infinite series formula or something, but I would not know what it is.
Pages: 1 2