Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2. Fibonacci numbers F1, F2, F3, . . . are defined by the rule: F1 = F2 = 1 and Fk = Fk−2 + Fk−1 for k > 2.
Lucas numbers L1, L2, L3, . . . are defined in a similar way by the rule: L1 = 1, L2 = 3 and Lk = Lk−2 + Lk−1 for k > 2.
Show that Fibonacci and Lucas numbers satisfy the following equality
for all n ≥ 2
Ln = Fn−1 + Fn+1.
How would I go about doing this?
 A: Since you wanted the proof by induction: 
Note we adapt the usual procedure of induction: Instead of assuming the proposition is true for an arbitrary value of n implies it is true for (n+1), we show if the proposition is true for BOTH n AND (n+1) then it is true for (n+2). Of course the Base Case now will require us to verify the proposition is true for two consecutive values of n.
Base Case: Clearly 3=1+2 so the claim L(n)=F(n-1)+F(n+1) is certainly true when n=2. I leave you to show that the claim is also true when n=3 (this is very easy).
Inductive Hypotheses:
Assume for some natural number 'n' that 
L(n)=F(n-1)+F(n+1) and 
L(n+1)=F(n)+F(n+2) 
Add the two equations:
L(n)+L(n+1)=[F(n)+F(n-1)] + [F(n+1)+F(n+2)]
but by definition L(n)+L(n+1) = L(n+2)
and similarly F(n)+F(n-1) = F(n+1)
So we deduce L(n+2)=F(n+1)+F(n+3), hence the inductive step is complete.
I hope you understand the proof by induction?
A: Proof by induction is the most obvious way to proceed for this problem. However in case you have not yet studied proof by induction (or do not wish to use it for whatever reason) you could use Binet's Formula for Fibonacci and Lucas Numbers (see the references below) for a direct proof.
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
http://en.wikipedia.org/wiki/Lucas_number
In case you help with the proof: let a = (1 + 5^(1/2))/2 and b = (1-5^(1/2))/2. 
Then by Binet's formulae in the references above, L(n) = a^n +b^n and 
F(n) = 5^(-1/2)*(a^n - b^n). 
Then F(n+1) + F(n-1) = 5^(-1/2)*[(a^(n+1) + a^(n-1) - (b^(n+1) + b^(n-1))]
But (a^(n+1) + a^(n-1)) = a^(n-1)(1+a^2) and (b^(n+1) + b^(n-1)) = b^(n-1)(1+b^2).
But using the fact that a = (1 + 5^(1/2))/2 we can easily show that (1+a^2) = 5^(1/2)*a and similarly  (1+b^2) = -5^(1/2)*b. I leave the last step for you to complete.
