Results 1 to 2 of 2

Math Help - Fibonacci Proof Help

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    Canada
    Posts
    1

    Fibonacci Proof Help

    Consider the recursion Fk = Fk−1 + Fk−2, k ≥ 2, with F0 = 0 and F1 = 1. Prove
    that Fk is even if and only if 3 | k. In other words, prove that, modulo 2, F3t = 0,
    F3t+1 = 1, and F3t+2 = 1 for t ≥ 0.

    I'm just having some trouble solving the above proof. I see why it works (because odd + odd = even, even + odd = odd, etc), but I cannot prove it with induction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Fibonacci Proof Help

    Hey macmee.

    Instead of looking at each individual step, look at each set of paired steps and prove that each paired step has only one even and odd result in that pair and that the order of each pair (in terms of being even or odd) is the same for each pair.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 6th 2012, 12:41 AM
  2. Fibonacci Proof II
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2011, 03:04 AM
  3. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 5th 2009, 08:08 AM
  4. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2008, 05:12 PM
  5. Fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:36 AM

Search Tags


/mathhelpforum @mathhelpforum