# Proving Lucas Numbers and Fibonacci Numbers

• Mar 18th 2008, 07:10 AM
hockey777
Proving Lucas Numbers and Fibonacci Numbers
The Lucas numbers $l_{0}, l_{1}, l_{2},...,l_{n}...$ are defined on the same recurrence relation defining the Fibonacci numbers, but the Lucas numbers posses different initial conditions.

$l_{n}=l_{n-1} + l_{n-2},$ (n≥2), $l_{0}=2, l_{1} = 1$

(a) $l_{n} = f_{n-1} + f_{n+1}$ for n≥1.

My hardest part is getting started. I don't really know how I can start off relating these two functions.

EDIT:
I don't know why I didn't think of this (mind isn't all there today), but I can use induction, correct?
• Mar 18th 2008, 08:08 AM
hockey777
So Let n=1
$l_{1}=f_{0}+f_{2}$
1 = 0 +1

Check

Assume $l_{n}=f_{n-1}+f_{n+1}$

$l_{n+1}$= $l_{n} + l_{n-1}$ stated in our first assumption

$l_{n}= f_{n-1}+f_{n+1}$ and * $l_{n-1}=f_{n-1}+f_{n+1}$*

$l_{n+1}=f_{n-1}+f_{n+1} +f_{n-1}+f_{n+1}$

then by simplifying with Fibonacci Identities I get

$l_{n+1} = f_{n} + f_{n+2}$ for n≥1.

My question now is with the part between the **, can I make that assumption based on my induction assumption since that is n-1 and my induction assumption is n.
• Mar 18th 2008, 11:33 PM
CaptainBlack
Quote:

Originally Posted by hockey777
So Let n=1
$l_{1}=f_{0}+f_{2}$
1 = 0 +1

Check

Assume $l_{n}=f_{n-1}+f_{n+1}$

$l_{n+1}$= $l_{n} + l_{n-1}$ stated in our first assumption

$l_{n}= f_{n-1}+f_{n+1}$ and * $l_{n-1}=f_{n-1}+f_{n+1}$*

$l_{n+1}=f_{n-1}+f_{n+1} +f_{n-1}+f_{n+1}$

then by simplifying with Fibonacci Identities I get

$l_{n+1} = f_{n} + f_{n+2}$ for n≥1.

My question now is with the part between the **, can I make that assumption based on my induction assumption since that is n-1 and my induction assumption is n.

Use strong induction, then the assumption is that:

$l_{k}=f_{k-1}+f_{k+1} ~\forall k \in [1,n]$ for some $n > 1$

RonL