Results 1 to 4 of 4

Math Help - Fibonacci proof

  1. #1
    asc
    asc is offline
    Newbie
    Joined
    Dec 2007
    Posts
    8

    Fibonacci proof

    The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

    Plz give a counting prof instead of induction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by asc View Post
    The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

    Plz give a counting prof instead of induction.
    Can use fibonacci formula??
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by asc View Post
    The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

    Plz give a counting prof instead of induction.
    We want to prove f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1} for n\geq 1.
    Which is true for n=1. Suppose it is true for all k\leq n. Then f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by ThePerfectHacker View Post
    We want to prove f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1} for n\geq 1.
    Which is true for n=1. Suppose it is true for all k\leq n. Then f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n
    The original poster wrote
    Plz give a counting prof instead of induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 02:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 28th 2009, 10:21 PM
  3. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2009, 08:31 AM
  4. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2008, 05:12 PM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum