Results 1 to 3 of 3

Thread: 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:
    $\displaystyle f_{n} = f_{n-1} + f_{n-2}$
    Using induction, prove that $\displaystyle f_{3n}$ is a even number for all $\displaystyle 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
    4
    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:
    $\displaystyle f_{n} = f_{n-1} + f_{n-2}$
    Using induction, prove that $\displaystyle f_{3n}$ is a even number for all $\displaystyle 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 $\displaystyle F_0=0,\;\;\;F_1=1$

    $\displaystyle F_2=Even+Odd=Odd$

    $\displaystyle F_3=Odd+Odd=Even$

    $\displaystyle F_4=Even+Odd=Odd$

    $\displaystyle F_5=Odd+Even=Odd$

    $\displaystyle F_6=Odd+Odd=Even$

    the pattern is for n=0, 1, 2, 3, 4.... $\displaystyle 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 $\displaystyle F_0$


    P(k)

    $\displaystyle F_{3n}=Even$

    P(k+1)

    $\displaystyle F_{3(n+1)}=Even$

    Proof

    $\displaystyle F_{3(n+1)}=F_{3n+3}$

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

    and so it is Even if $\displaystyle 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: Jan 19th 2011, 03:41 PM
  2. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 2nd 2010, 01:01 AM
  3. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 14th 2009, 07:38 AM
  4. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 23rd 2008, 05:19 PM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Aug 27th 2008, 10:19 AM

/mathhelpforum @mathhelpforum