# Thread: Proving Lucas Numbers and Fibonacci Numbers

1. ## Proving Lucas Numbers and Fibonacci Numbers

The Lucas numbers $\displaystyle 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.

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

(a)$\displaystyle 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?

2. So Let n=1
$\displaystyle l_{1}=f_{0}+f_{2}$
1 = 0 +1

Check

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

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

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

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

then by simplifying with Fibonacci Identities I get

$\displaystyle 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.

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

Check

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

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

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

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

then by simplifying with Fibonacci Identities I get

$\displaystyle 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:

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

RonL