Homework Help: Lucas Numbers/ Fibonacci Numbers Proof

1. Feb 4, 2010

cwatki14

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. Feb 4, 2010

JSuarez

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.

3. Feb 4, 2010

cwatki14

Is it that the proof completely lacks a base case and just assumes it is true up to k+1?

4. Feb 4, 2010

VeeEight

Yes. You need to show a base case works in order to apply the induction hypotheis.