Results 1 to 2 of 2

Math Help - Fibonacci number Induction Proof

  1. #1
    Newbie Pi R Squared's Avatar
    Joined
    Oct 2009
    Posts
    13

    Question Fibonacci number Induction Proof

    Prove every third Fibonacci number is even.-- The Fibonacci numbers are the sequence 1,1,2,3,5,8,13,..., given by f_n where f(1)=1, and f(2)=1, and f_(n)=f(n-1)+(n-2)( for all n.

    This is the problem...

    This is what I have...
    Base Case:
    f(3k-2) if k=1 then f(3(1)-2)=f(1)=1 odd #
    f(3k-1) f(3(1)-1)=f(2)=1 odd #
    f(3k) f(3(1) =f(3)=2 even #

    so f(1)+f(2)=f(3)
    an odd+odd=even

    Inductive step:

    Suppose it is true for k+1
    f(3(k+1)-2)=f(3k+1)
    f(3(k+1)-1)=f(3k+2)
    f(3(k+1)) =f(3K+3)


    I do not know where to go from here...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    First let me note that it's very good that you made your induction statement (let's call it P(k)) consist of three parts:

    P(k) is ( f(3k-2) is odd) and ( f(3k-1) is odd) and ( f(3k) is even)

    The original assertion to prove (let's call it Q(k)) is just:

    Q(k) is ( f(3k) is even)

    However, this is not enough to prove the induction step, which is the following statement:

    for all k \ge 1, Q(k) implies Q(k+1)

    Knowing Q(k) just is not enough to be able to prove Q(k+1). Therefore, we strengthen the induction statement from Q(k) to P(k). Now, in proving that P(k) implies P(k+1), we have more to prove (three substatements of P(k+1) instead of just one of Q(k+1)), but we also have a stronger assumption P(k). This technique -- strengthening the induction statement in order for the induction step to go through -- is very common in mathematics.

    End of a long digression. Concerning your proof, why do you say "Suppose it is true for k+1"? Inductive step is usually "suppose it is true for k; we need to prove it for k+1", i.e., one has to prove P(k) implies P(k+1) for all k\ge 1. So write carefully what you know, i.e., P(k), and what you need to prove, i.e., P(k+1), and the proof should be pretty straightforward.
    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. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 11:22 AM
  3. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 07:28 AM
  4. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 08:38 AM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 11:19 AM

Search Tags


/mathhelpforum @mathhelpforum