Results 1 to 2 of 2

Math Help - Induction w/ Fibonacci

  1. #1
    Newbie bakerconspiracy's Avatar
    Joined
    Mar 2009
    Posts
    20

    Induction w/ Fibonacci

    The question is prove that fn < 2^n, where fn is the nth number in the Fibonacci sequence.

    I got the first steps,

    For n = 3, fn = f(n-1) + f(n-2) = 1 + 1 < 2^3 = 2^n.

    Assume fn < 2^n for some n. Now for n+1...

    This is where I have the trouble. I'm pretty sure I have to use strong induction and break down the nth Fibonacci number, but I've been stuck on this one.

    Any help is appreciated, Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by bakerconspiracy View Post
    The question is prove that fn < 2^n, where fn is the nth number in the Fibonacci sequence.

    I got the first steps,

    For n = 3, fn = f(n-1) + f(n-2) = 1 + 1 < 2^3 = 2^n.

    Assume fn < 2^n for some n. Now for n+1...


    ...for n+1 we have F_{n+1}=F_n+F_{n-1}<2^n+2^{n-1}<2^n+2^n=2^{n+1} and you're done

    Tonio


    This is where I have the trouble. I'm pretty sure I have to use strong induction and break down the nth Fibonacci number, but I've been stuck on this one.

    Any help is appreciated, Thanks.
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Induction Proofs
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 4th 2010, 09:39 AM
  2. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  3. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM
  4. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 10:19 AM
  5. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum