Results 1 to 2 of 2

Thread: 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 $\displaystyle f_n$ where $\displaystyle f$(1)=1, and $\displaystyle f$(2)=1, and $\displaystyle f_(n)=f(n-1)+(n-2)($ for all $\displaystyle 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,577
    Thanks
    790
    First let me note that it's very good that you made your induction statement (let's call it $\displaystyle P(k)$) consist of three parts:

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

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

    $\displaystyle Q(k)$ is ($\displaystyle f(3k)$ is even)

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

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

    Knowing $\displaystyle Q(k)$ just is not enough to be able to prove $\displaystyle Q(k+1)$. Therefore, we strengthen the induction statement from $\displaystyle Q(k)$ to $\displaystyle P(k)$. Now, in proving that $\displaystyle P(k)$ implies $\displaystyle P(k+1)$, we have more to prove (three substatements of $\displaystyle P(k+1)$ instead of just one of $\displaystyle Q(k+1)$), but we also have a stronger assumption $\displaystyle 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 $\displaystyle P(k)$ implies $\displaystyle P(k+1)$ for all $\displaystyle k\ge 1$. So write carefully what you know, i.e., $\displaystyle P(k)$, and what you need to prove, i.e., $\displaystyle 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: Jan 19th 2011, 03:41 PM
  2. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Oct 1st 2010, 10:22 AM
  3. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 18th 2010, 06:28 AM
  4. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 14th 2009, 07:38 AM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Aug 27th 2008, 10:19 AM

Search Tags


/mathhelpforum @mathhelpforum