The Lucas numbers are defined recursively by the formulas
L1 = 1, L3 = 3, and for all n ≥ 3, Ln = Ln-1 + Ln-2.
The first few Lucas numbers are
1, 3, 4, 7, 11, 18...
This definition is similar to that of the Fibonacci numbers Fn, except that F1 = and F2 = 1
Using induction, prove that for all integers, n > 1,
Ln = Fn-1 + Fn+1.
You may need to recall that the Fibonacci numbers are the sequence, {Fn}, that is defined via the formula:
F1 = 1, F2 = 1, and for all n ≥ 3, Fn = Fn-1 + Fn-2.
Hint. When you work on this, you'll likely find that you need to know not only information about the k-th Lucas number, but also the (k-1)-th Lucas number. Don't forget to correctly identify what is your conditional statement, P(k)! You should adjust your induction steps accordingly:
new base cases: you need to show that both P(2) and P(3) are true.
new inductive hypothesis: given k ∈ N generic and k ≥ 3, assume that P(k-1) and P(k) are both true.
new inductive step: prove that P(k+1) is true.