Results 1 to 5 of 5

Math Help - Fibonacci sequence divisibility proof

  1. #1
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Question Fibonacci sequence divisibility proof

    Hello All,

    I am thoroughly lost with how to construct this proof:

    Let F(sub)n be the nth Fibonacci number.

    Prove that, if 3|n then 2|F(sub)n.


    Would induction be a recommendation, and if so, could anyone please recommend a base assumption to begin with?

    Thank you very much for your time,

    Panglot
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Fibonacci sequence divisibility proof

    Quote Originally Posted by panglot View Post
    Hello All,

    I am thoroughly lost with how to construct this proof:

    Let F(sub)n be the nth Fibonacci number.

    Prove that, if 3|n then 2|F(sub)n.


    Would induction be a recommendation, and if so, could anyone please recommend a base assumption to begin with?

    Thank you very much for your time,

    Panglot

    If and only if can be placed.


    Are you familiar with the theorem that says:

    F_m|F_n if and only if m|n.
    Last edited by Also sprach Zarathustra; June 18th 2011 at 10:44 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Fibonacci sequence divisibility proof

    What you want to prove is that
    F_{3n}
    is divisible by 2 for any positive integer n. It is easy to do that by induction on n.

    If n= 1,
    F_{3(1)}= F_3= 2
    which is divisible by 2.

    Assume that, for some k,
    F_{3k}
    is divisible by 2. That is, that
    F_{3k}= 2m
    for some integer m.

    Then
    F_{3(k+1)}= F_{3k+ 3}= F_{3k+1}+ F_{3k+2}= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Re: Fibonacci sequence divisibility proof

    Quote Originally Posted by HallsofIvy View Post
    What you want to prove is that
    F_{3n}
    is divisible by 2 for any positive integer n. It is easy to do that by induction on n.

    If n= 1,
    F_{3(1)}= F_3= 2
    which is divisible by 2.

    Assume that, for some k,
    F_{3k}
    is divisible by 2. That is, that
    F_{3k}= 2m
    for some integer m.

    Then
    F_{3(k+1)}= F_{3k+ 3}= F_{3k+1}+ F_{3k+2}= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}.
    I'm sorry, but I don't quite follow how you arrived at the last two in the series of equivalences:

    = F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Fibonacci sequence divisibility proof

    Quote Originally Posted by panglot View Post
    I'm sorry, but I don't quite follow how you arrived at the last two in the series of equivalences:

    = F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}
    By definition of Fibonacci sequence.

    F_{k+2}=F_{k+1}+F_{k}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 5th 2011, 02:29 AM
  2. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  3. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2010, 07:28 AM
  4. Fibonacci Sequence Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 15th 2009, 07:40 PM
  5. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 30th 2007, 09:12 AM

Search Tags


/mathhelpforum @mathhelpforum