Results 1 to 3 of 3

Math Help - Fibonacci sequence induction proof

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    Fibonacci sequence induction proof

    Hi!
    I have a assignment involving the fibonacci sequence, and I wonder if anyone could give me a hand with it:
    The fibonacci sequence is given as:
    f_{n} = f_{n-1} + f_{n-2}
    Using induction, prove that f_{3n} is a even number for all n \in \mathbb{N}

    I have been struggeling with this for some days now. One of my questions is how do I express the fact that the answer is a even number mathematically? Do I even need to?

    Any help would be much appreciated!
    Martin
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    769
    "One of my questions is how do I express the fact that the answer is a even number mathematically?" Let n = 2k
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by masterk View Post
    Hi!
    I have a assignment involving the fibonacci sequence, and I wonder if anyone could give me a hand with it:
    The fibonacci sequence is given as:
    f_{n} = f_{n-1} + f_{n-2}
    Using induction, prove that f_{3n} is a even number for all n \in \mathbb{N}

    I have been struggeling with this for some days now. One of my questions is how do I express the fact that the answer is a even number mathematically? Do I even need to?

    Any help would be much appreciated!
    Martin
    With F_0=0,\;\;\;F_1=1

    F_2=Even+Odd=Odd

    F_3=Odd+Odd=Even

    F_4=Even+Odd=Odd

    F_5=Odd+Even=Odd

    F_6=Odd+Odd=Even

    the pattern is for n=0, 1, 2, 3, 4.... F_{3n}=Even

    Since the first 2 terms are even and odd, we never encounter two successive even numbers in the Fibonacci sequence.

    The Fibonacci sequence pattern is EOOEOOEOOEOOEOO starting at F_0


    P(k)

    F_{3n}=Even

    P(k+1)

    F_{3(n+1)}=Even

    Proof

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

    every Even term is followed by 2 Odd terms, hence F_{3n+3} is the 3rd term after F_{3n}

    and so it is Even if F_{3n} is Even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 04:41 PM
  2. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 2nd 2010, 02:01 AM
  3. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 08:38 AM
  4. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 23rd 2008, 06:19 PM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 11:19 AM

/mathhelpforum @mathhelpforum