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!

Homework Help: 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