Results 1 to 4 of 4

Math Help - Fibonacci numbers with negative indices

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    5

    Fibonacci numbers with negative indices

    Let the Fibonacci sequence Fn be defined by its recurrence relation (1) Fn=F(n-1)+F(n-2) for n>=3. Show that there is a unique way to extend the definition of Fn to integers n<=0 such that (1) holds for all integers n, and obtain an explicit formula for the terms Fn with negative indices n.

    I am completely stuck on how to prove this by induction. I figured that Fn = Fn+2-Fn+1, but i don't know how to apply induction to this to prove it for all integers n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The recursive computation f_{n}= f_{n+2} - f_{n+1} is perfectly possible. Starting with f_{1}=f_{0}=1 we obtain...

    f_{-1} = f_{1} - f_{0} = 0

    f_{-2} = f_{0} - f_{-1} = 1

    f_{-3} = f_{-1} - f_{-2} = -1

    f_{-4} = f_{-2} - f_{-3} = 2

    f_{-5} = f_{-3} - f_{-4} = -3

    f_{-6} = f_{-4} - f_{-5} = 5

    f_{-7} = f_{-5} - f_{-6} = -8

    f_{-8} = f_{-6} - f_{-7} = 13

    \dots

    It seems that the 'negative sequence' replies, with alternating signs, the 'positive sequence'...

    Kind regards

    \chi  \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    5
    Thanks Chisigma! But how would one prove this using induction? Thats the part that really bugs me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by morbius27 View Post
    Let the Fibonacci sequence Fn be defined by its recurrence relation (1) Fn=F(n-1)+F(n-2) for n>=3. Show that there is a unique way to extend the definition of Fn to integers n<=0 such that (1) holds for all integers n, and obtain an explicit formula for the terms Fn with negative indices n.

    I am completely stuck on how to prove this by induction. I figured that Fn = Fn+2-Fn+1, but i don't know how to apply induction to this to prove it for all integers n
    You have that f_n=f_{n-1}+f_{n-2}. This is a homogenous linear recurrence relation. That said, it's solution is of the form f_n=C_1 \alpha^n+C_2 \beta^n. Where \alpha,\beta are the solutions the auxiliary polynomial x^2-x-1=0 and C_1,C_2 are determined by initial conditions.

    It turns out that f_n=\frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}} where \varphi is the golden ratio.

    This is clearly a canonical way to extend f_n to \mathbb{Z}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Negative indices
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: March 20th 2011, 09:57 AM
  2. Negative fractional indices
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 18th 2010, 03:08 PM
  3. negative indices
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 14th 2009, 10:39 PM
  4. Replies: 3
    Last Post: December 14th 2008, 05:54 AM
  5. Negative Indices
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 13th 2008, 02:49 PM

Search Tags


/mathhelpforum @mathhelpforum