Negative Fibonacci numbers

Discussion in 'Recreational Math' started by walt, Apr 3, 2005.

  1. walt

    walt Guest

    Okay, you brainiacs, you got my attention with your answers
    to my last question, so here's a follow-up for you.

    If, instead of extending the Fib series on out to infinity,
    you extend it backwards into the negative range, you get
    this:

    ....13 8 5 3 2 1 1 0 1 -1 2 -3 5 -8 13 -21...

    I can't imagine I'm the first to think of this. Anyone know
    who might have been the first, and if it generated any
    interesting results?

    I like to think there may be a connection between this series
    and the oscillation described by e^ix but I can't take the
    idea any farther than that.
     
    walt, Apr 3, 2005
    #1
    1. Advertisements

  2. walt

    Proginoskes Guest

    Technically, ... -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 ...
    The formula for this double-infinite sequence is still
    F(n) = A * B^n - A * C^n, where A = 1/sqrt(5), B = (1+sqrt(5))/2,
    and C = (1-sqrt(5))/2, except that n can be negative here.
    I think it has more to do with the conjugate of an expression like
    a + b sqrt(c), since the minus sign shows up when you evaluate

    1/(a + b sqrt(c))
    = (a - b sqrt(c)) / [(a + b sqrt(c))(a - b sqrt(c))]
    = (a - b sqrt(c)) / (a^2 - b^2 c)
    = a / (a^2 - b^2 c) - [b / (a^2 - b^2 c)] sqrt(c).

    --- Christopher Heckman
     
    Proginoskes, Apr 3, 2005
    #2
    1. Advertisements

  3. walt

    walt Guest

    I see two possiblities:

    1) You are left-handed.
    2) You are prejudiced against left-handed people.

    Which is it?
     
    walt, Apr 4, 2005
    #3
  4. walt

    Marc Olschok Guest

    I do not have literature within reach, but you may find somthing
    in Vol 1 of D.E.Knuth 'The art of computer programming'.
    There is a chapter on Fibonacci numbers, where he also mentions
    the matrix equation

    ( f_(n+1) f_n )
    ( ) = A^n
    ( f_n f_(n-1)

    where A is the matrix
    ( 1 1 )
    ( 1 0 )

    Marc
     
    Marc Olschok, Apr 4, 2005
    #4
  5. walt

    Proginoskes Guest

    3) Society is (for the most part) right-handed.

    On the number line, positive numbers are to the right of the negative
    numbers. If you want to keep the recurrence as
    F(n+2) = F(n+1) + F(n), then you need to arrange the terms as
    .... -3 2 -1 1 0 1 1 2 3 5 8 ...

    To generate the sequence ... 8 5 3 2 1 1 0 1 -1 2 -3 ..., you need the
    recurrence
    F(n+2) = F(n+1) - F(n).

    --- Christopher Heckman
     
    Proginoskes, Apr 4, 2005
    #5
  6. walt

    walt Guest


    A mathematical answer to a non-mathematical question -- good work!

    This time I have a mathematical question for you (and all others):

    In my previous thread about Fibonacci numbers there were several
    references to this equation: phi^2 - phi - 1 = 0

    I'm able to derive that equation for myself from the definition of
    the 'Golden Ratio', based solely on geometry.

    But I'm stumped when trying to connect that quadratic equation to the
    Fibonacci series (or Lucas series, etc.).

    In what sense is this quadratic 'characteristic' of the Fib series, or
    of exponential growth? How is the connection made between a quadratic
    equation and an exponential curve? This is where my lack of formal
    mathematical training betrays me, alas.
     
    walt, Apr 5, 2005
    #6
  7. walt

    Dave Langers Guest

    In what sense is this quadratic 'characteristic' of the Fib series, or
    The Fibonacci recurrence is
    F(n) = F(n-1) + F(n-2)
    of course.

    Now suppose a certain exponential function g(n) = b^n satisfies this
    equation, then
    b^n = b^(n-1) + b^(n-2)
    b^n - b^(n-1) - b^(n-2) = 0
    Divide by b^(n-2) to get
    b^2 - b - 1 = 0
    So
    b = (1 +/- sqrt(5))/2

    Since the recursion is linear (i.e., if both a function g(n) and a
    function h(n) satisfy the equation, then any linear combination
    p*g(n)+q*h(n) satisfies the equation), we find a more general solution
    F(n) = p * ((1+sqrt(5))/2)^n + q * ((1-sqrt(5))/2)^n
    which will satisfy the recurrence for any p and q.
    Because both exponentials are linearly independent, and because we have
    two basisfunctions, we can satisfy any two initial conditions we want by
    means of suitable p and q. For instance, F(0)=F(1)=1. This gives the
    equation for the Fibonacci numbers in closed form.
     
    Dave Langers, Apr 5, 2005
    #7
  8. walt

    Hanford Carr Guest

    let r = F(n+1)/F(n)= (F(n) + F(n-1))/F(n) = 1 + F(n-1))/F(n)
    In the limit F(n-1))/F(n) = 1/r

    r = 1 + 1/r
    r^2 = r + 1
    r^2 - r - 1 = 0

    Cheers Hanford
     
    Hanford Carr, Apr 5, 2005
    #8
  9. walt

    Bob Pease Guest

    1> b^n = b^(n-1) + b^(n-2)
    2> b^n - b^(n-1) - b^(n-2) = 0
    3> Divide by b^(n-2) to get
    4> b^2 - b - 1 = 0


    b = (1 +/- sqrt(5))/2




    Even if n is not restricted restricted to integers
    This seems to imply that the only exponential functions of the form

    b^n = b^(n(1 +/- sqrt(5 which have any solution whatever must have a base
    of
    (1 +/- sqrt(5))/2

    This seems to say, informally, that any exponential growth which is
    Fibonaccian must have PHI as a base .

    Maybe myself and OP would like a quick non-mathematical reference about the
    Rabbit-growth Model vs the base "e" model.

    RJ P
     
    Bob Pease, Apr 5, 2005
    #9
  10. walt

    Dave Langers Guest

    Even if n is not restricted restricted to integers
    Yes.
    Furthermore, because (1+sqrt(5))/2 is the negative inverse of
    (1-sqrt(5))/2, the 'growth speed' in positive direction is the same as
    that in negative direction, except for the flipping signs.
    google is your friend.
     
    Dave Langers, Apr 5, 2005
    #10
  11. walt

    sttscitrans Guest

    One way is to think of the series
    G(x)= 1 +x +2x +3x^2 + ....f(n)x^x + ....

    G(x)= 1 +x +2x^2 +3x^3 + ....f(n)x^n + ....
    xG(x)= x + x^2 +2x^3 + f(n-1)x^n+ ...
    x^2G(x) = x^2 +x^3 + f(n-2)x^ + ...

    G(x) -xG(x) -x^2G(x) = 1

    G(x) = 1/(1 -x -x^2)

    = 1/((1-rx)(1-sx))
    = A/(1-rx) + B/(1-sx)

    = A(1 +rx +(rx)^2 + ....
    + B(1 =sx +(sx)^2 + ....

    So the coefficient of x^n,
    f(n)= Ar^n +Bs^n
     
    sttscitrans, Apr 9, 2005
    #11
  12. walt

    Alex.Lupas Guest

    Hi friends, perhaps of interest is a paper by Maurice d'OCAGNE
    ,,Sur une suite recurrente"
    published in
    Bulletin de la S.M.F., tome 14(1886) 20-41.

    See also

    http://www.numdam.org/item?id=BSMF_1886__14__20_1

    Regarding the above matrix: it was published in a note from
    MATHEMATICAL GAZETTE(arround 1970 ??). I try to find the exact reference.
    Using this matrix it's possible to find nice identitites for Fibonacci
    numbers by writing, e.g.
    A^{n+m}=A^n * A^m or det(A^n)= [det(A)]^n . (Try it !).
    For an arbitrary linear recurrence of second order
    X_{n+1}=aX_n+bX_{n-1}
    (a b)
    I have obtained, using the matrix (1 0) ,

    similar results. Regards,Alex
     
    Alex.Lupas, Apr 10, 2005
    #12
  13. walt

    Alex.Lupas Guest

    Hi,
    Some REFERENCES where above matrix is used :

    [1] J.R.Sylvester, Mathe.Gazette 63(1979) 188--191.

    [2] A. L. , Gazeta Matematica (Seria B),Anul 87, 11(1982)401-402.

    Comments:
    (1 1) (F_{n+1} F_n )
    [i)] If A is the matrix (1 0),then as was posted A^n=(F_n F_{n-1}).

    Because det(A)=-1 and det(A^n)=F_{n+1}*F_{n-1} -F_{n}^2 we find

    F_{n+1}*F_{n-1} -F_{n}^2= (-1)^n .
    This equality show us that the sequence (F_n) is not log-convex.

    Likewise, from A^nA^m=A^{n+m} follows the equality

    F_{n+m+1}=F_nF_m+F_{n-1}F_{m-1} .


    [ii)] Maurice d'OCAGNE defines ,,negative Fibonacci numbers" F_{-n}

    such that F_0=F_1=1 and

    (1) F_{z+1}= F_{z}+F_{z-1} for all z in Z(= the set of integers).
    ==============
    He observed that in this case F_{-n}=(-1)^{n+1}F_n , n=1,2, ....
    Indeed, from F_n = (-1)^{n+1}F_{-n} and F_{n+1}=F_n+F_{n-1} we find

    (-1)^{n+2}F_{-n-1}=(-1)^{n+1}F_{-n}+(-1)^{n}F_{-n+1} , that is

    F_{-n-1}= - F_{-n} +F_{-n+1} , or F_{-n+1}=F_{-n}+F_{-n-1} .

    [iii)] For a>-1,b>-1 denote by R_n=R_n^{(a,b)} the so-called Jacobi
    polynomial of degree n normalized by R_n^{(a,b)}(1)=1 . Some nice
    examples are:
    (a,b)=(-1/2,-1/2) then R_n(x)=T_n(x)=cos(n*arccos x)
    (a,b)=(0,0) then R_n is the Legendre polynomial
    (a,b)=(1/2,1/2) then R_n is U_n(x)= Chebychev polynomial of second kind.
    Because R_n^{(a,b)}(x)= F(-n,n+a+b+1;a+1; (1-x)/2 ) where
    F(A,B:C;z)= the GAuss hypergeomnetric function, i.e.
    F(A,B;C;z)= SUM_{k=0 to k=infty}(A)_k(B_k)*z^k/(k! *(C)_k) ,

    [ (A)_k :=A(A+1)...(A+k-1) ] we find
    ===============================
    (2) U_n(x)=F(-n,n+2;3/2; (1-x)/2) .
    ===============================
    Note that for x in (-1,1) holds the equality

    U_{n}(x)= sin((n+1)*arccos x)/((n+1)*sqrt(1-x^2)) .

    On the other hand it may be shown that

    (3) F_n=n*i^{n-1}*U_{n-1}(-i/2) , n>=1 , (i:=sqrt(-1) ).

    According to (2)-(3) it may be observed that , after d'Ocagne

    the numbers (F_z), z in Z={ ...,-3,-2,-1,0,1,2,...} may be defined

    as F_0=1 and for |z|>=1

    F_z = |z|*(i*sign(z))^{n-1}*U_{|z|-1}(-i/2)

    with sign(z)=1 for z>=1 and sign(z)=-1 if z<=-1 .

    [Note: U_m(-z)=(-1)^m *U_m(z) .]

    My question is how it's possible, using the hypergeometric form (2), to

    extend the Fibonacci numbers to the function f:R---R such that f(0)=1

    and f(r+1)=f(r)+f(r-1) for all real r . Which are the solutions,

    [if exists]of this functional equation.

    What about the set of numbers (L_z) where

    L_z=(A|z|+B)*(i*sign(z))^{n}*R_|z|^{(a,a}}(-i/2) , z in Z ??

    where A,B are integers and a in (-1,inft).

    Note that for A=0,B=2 , (a,a)=(-1/2,-1/2), z>=0,

    one finds Lucas numbers.

    When A=1,B=0, (a,a)=(1/2,1/2) , z>=0 ,we obserev that L_z=F_{z+1} .
    Alex
     
    Alex.Lupas, Apr 10, 2005
    #13
  14. walt

    Marc Olschok Guest

    Ah that is a fine reference and should settle the 'negative' part.
    If I have time, I should look in Knuths Book; most likely he has
    provided a reference.

    Thanks again,

    Marc
     
    Marc Olschok, Apr 14, 2005
    #14
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.