Possible Duplicate:
Prove this formula for the Fibonacci Sequence
How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$
How do I go about obtaining a closed formula for Lucas numbers?
The Lucas numbers $ L_n $ are defined by $L_1 = 1$, $L_2 = 3$, and $L_n = L_{n-1} + L_{n-2}$.
I tried looking into it on my discrete math textbook but I'm really confused. Maybe someone can lay out the steps for it?