Results 1 to 6 of 6

Math Help - Math induction: Fibonacci Numbers

  1. #1
    Junior Member
    Joined
    Jul 2009
    Posts
    69

    Math induction: Fibonacci Numbers

    The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by  a_0 =1, a_1 =1 and for n >2 by  a_n=a_{n-2}+ a_{n-1} .
    Show by induction that a_{3n} is even.


    base case: n=3 is 2, so it is even.
    Assume  a_n=a_{n-2}+ a_{n-1} is even?
    not sure how to do the induction step.

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    you can use the fact that \textrm{even} + \textrm{odd} = \textrm{odd} and \textrm{odd} + \textrm{odd} = \textrm{even}. This will allow you to set up an induction step.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    Posts
    144
    I believe that the inductive step would be a3n is even. You must prove that a3(n+1) which equals a3n+3 is even.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2009
    Posts
    69
    Quote Originally Posted by MATNTRNG View Post
    I believe that the inductive step would be a3n is even. You must prove that a3(n+1) which equals a3n+3 is even.
    If i want to prove  a_3n is even, should the induction step be  a_3(n-1) be even?

    And should i assume that  a_{n-2} and a_{n-1} are odd?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    Posts
    144
    You are assuming that a3n is even as your inductive hypothesis and you want to prove that a3(n+1) is even to complete your proof, i believe. Sorry, I wish I could help you more but I am not sure where to go from here...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by firebio View Post
    The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by  a_0 =1, a_1 =1 and for n >2 by  a_n=a_{n-2}+ a_{n-1} .
    Show by induction that a_{3n} is even.


    base case: n=3 is 2, so it is even.
    Assume  a_n=a_{n-2}+ a_{n-1} is even?
    not sure how to do the induction step.

    Thanks in advance
    The Fibonacci sequence, in terms of odd and even is...

    OOEOOEOOEOOEOOEOOE.....

    This is because the first 2 terms are odd
    odd+odd=even=3rd term
    odd+even=odd=4th term
    even+odd=odd=5th term
    odd+odd=even=6th term

    The sequence cycles in this way

    Hence if

    a_{3n}=Even

    The inductive step is..... does a_{3n} being even cause a_{3(n+1)} to be even ?

    a_{3(n+1)}=a_{3n+3}

    a_{3n+3}=a_{3n+1}+a_{3n+2}

    Proof

    If a_{3n} is even, then both a_{3n+1} and a_{3n+2} must of necessity both be odd.

    Hence, as this is true, and a_{3} is even, a_{3n} is even.

    The inductive proof is really just basic logic in this case!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] induction problem with fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 5th 2011, 09:00 PM
  2. Strong induction on Fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 27th 2010, 11:00 AM
  3. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  4. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 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