Results 1 to 2 of 2

Math Help - Fibonacci number Induction Proof

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

    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)) =f(3K+3)

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

  2. #2
    MHF Contributor
    Oct 2009
    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