Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lucas Numbers/ Fibonacci Numbers Proof

  1. Feb 4, 2010 #1
    Here's the question:
    The Lucas numbers Ln are defined by the equations L1=1 and Ln=Fn+1 + Fn-1 for each n>/= 2. Fn stands for a fibonacci number, Fn= Fn=1 + Fn-2. Prove that
    Ln=Ln-1+Ln-2 (for n>/= 3)
    So I did the base case where n=3, but I am stuck on the induction step... Any ideas?
    Then the problem asks "what is wrong with the following argument?"
    "Assuming Ln=Fn for n=1,2,...,k we see that
    Lk+1=Lk=Lk-1 (by the above proof)
    =Fk+Fk-1 (by our assumption)
    =Fk+1 (by definition of Fk+1)
    Hence by the principle of mathematical induction Fn=Ln for each positive n."

    Any help would be greatly appreciated!
  2. jcsd
  3. Feb 4, 2010 #2
    For the induction step, express L(n-1) and L(n-2) in terms of Fibonacci numbers (using the induction hyphotesis) and recombine the terms.

    The base case.
  4. Feb 4, 2010 #3
    Is it that the proof completely lacks a base case and just assumes it is true up to k+1?
  5. Feb 4, 2010 #4
    Yes. You need to show a base case works in order to apply the induction hypotheis.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook