1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Induction

Tags:
  1. Feb 13, 2015 #1
    1. The problem statement, all variables and given/known data
    The fibonacci numbers are defined by F0 = 0 F1 = 1 and Fn = n-1 + Fn-2 for n >= 2.
    Use induction the prove the following:
    Fn-1Fn+1 - Fn = (-1)n

    The attempt at a solution
    Let P(n) = Fn-1Fn+1 - Fn2 = (-1)n where n>= 1

    Show it holds for first natural number:
    P(1) = F0 + F2 - F12 = -(1) = -1. So it is true

    Now assume it works for some k and prove it works for k+1
    This is where I'm really not sure what to do. I have tried putting
    F(k+1)-1F(k+1)+1 - F(k+1)2 but it ultimately gets me no where.

    Usually when I have done inductive proofs I start with some sequence of numbers 1,2,3,4.....,n and show n+1 is there but this one seems slightly different and I'm not sure how to proceed.

    Any help is appreciated.
     
  2. jcsd
  3. Feb 13, 2015 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You want terms involving ##F_k##, ##F_{k+1}##, and ##F_{k-1}##, so use the defining relation to rewrite ##F_{k+2}##.
     
  4. Feb 14, 2015 #3
    Thank you for your reply.

    With that I get:
    FkFk+2 - F2k+1

    Fk(Fk+1 + Fk) - F2k+1

    FkFk+1 + F2k - F2k+1

    Fk+1(Fk - Fk+1) + F2k

    I'm not really sure where to go from this point.
    Just to verify that I am thinking of this the right way.
    I am trying to find a spot that I can use the assumption made about k where (Fk-1Fk+1 - F2k) and link that to k+1 correct?
     
    Last edited: Feb 14, 2015
  5. Feb 14, 2015 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Yes, that's what you're trying to do. You need to play around with it a bit. The ##F_{k+1}^2## term isn't one you want around, right? What can you do with it?
     
  6. Feb 14, 2015 #5
    Okay so this is what I got:
    Fk+1(Fk - Fk-1) + F2k

    Fk+1(Fk - Fk - Fk - 1) + F2k

    -Fk+1Fk-1 + F2k

    Multiply by -1 and get:

    Fk+1Fk-1 - F2k = -(-1)k+1

    So P(k) = -(-1)k+1

    The part about the -1 on the right hand side threw me off at the end but I think it makes sense.

    It seems unusual that this is proving k+1 though because it ends with P(k)

    And again thank you for your help I have been looking at this problem for longer than I would care to admit.
     
  7. Feb 14, 2015 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    I'm not sure what you did here. It looks like you introduced a term out of thin air.
     
  8. Feb 15, 2015 #7
    I made a mistake when I was typing. It should have said Fk+1(Fk - Fk+1) + F2k

    Then I used the defining relation on Fk+1 to get the next line.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by Induction
  1. Proof by induction (Replies: 6)

  2. Inductive proof (Replies: 9)

  3. Proof by induction (Replies: 2)

  4. Proof by induction (Replies: 9)

  5. Proof by induction (Replies: 32)

Loading...