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
    10
    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, 03:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 28th 2009, 11:21 PM
  3. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2009, 09:31 AM
  4. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2008, 06:12 PM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 08:10 AM

Search Tags


/mathhelpforum @mathhelpforum