Results 1 to 2 of 2

Math Help - Recurrence and Fibonacci sequence

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    Recurrence and Fibonacci sequence

    Hi. I have this problem that im stuck on.

    Define a sequence (G_n)_{n \ge0} by the recurrence G_n = G_{n-1}+G_{n-2} for n \ge2. Subject to the initial values G_0=2, G_1=1. Let (F_n)_{n \ge0} denote the Fibonacci sequence.

    a) Write out explicitly (G_n)_{n=0,...,10}
    I think this is easy.
    {2,1,3,4,7,11,18,29,47,76}

    b) Prove that G_n=F_{n-1}+F_{n+1}, n\ge1
    How do I go about it?
    I know F_0=0 and F_1=1 and F_2=1 and F_3=2
    So if n=1, G_1=F_0+F_3=1+2=3, so it looks like its true.But how do I prove it explicitly?\

    c) Let \tau= \frac{1+ \sqrt{5}}{2} denote the golden ratio. Show G_n= \tau^n+(-\tau)^{-n}
    I'm just a bit lost in this one...

    d) The Fibonacci sequence counts pavings by monomers and dimers of an n-board. Conjecture what sort of pavings the sequence (G_n)_{n \ge1} counts?Draw the objects corresponding to G_3.
    G_3=G_2+G_1
    G_3=3+1=4
    But I'm not quite sure what it counts...

    Any help would be great. Thank-you so much!!
    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
    In...

    http://www.mathhelpforum.com/math-he...ce-154056.html

    ... it has been demonstrated that the general solution of the difference equation...

    x_{n} = x_{n-1} + x_{n-2} (1)

    ... is...

    \displaystyle x_{n}= c_{1} (\frac{1-\sqrt{5}}{2})^{n} + c_{2} (\frac{1+\sqrt{5}}{2})^{n} (2)

    If You start setting x_{0}= 0 and x_{1}=1 You obtain the 'Fibonacci sequence'. If You set x_{0}=2 and x_{1}=1 and You obtain the 'G sequence'...

    Kind regards

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

Similar Math Help Forum Discussions

  1. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 28th 2010, 03:54 AM
  2. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  3. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 11:47 PM
  4. Fibonacci sequence
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 26th 2009, 08:28 PM
  5. Fibonacci sequence
    Posted in the Algebra Forum
    Replies: 4
    Last Post: June 4th 2008, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum