Im working on practice problems that the instructor gave us yesterday, and I absolutely have no clue of how to solve this problem.. I need to use mathmatical induction to solve this problem..
The question is:
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 should I solve this problem using mathematical induction? I found a similar question to this but it was solved by using other method... I need to solve this using induction..
Detailed explanation will be very much appreciated..
I assume you can show it is true for $n=1$ and $n=2$, or for $n=2$ and $n=3$, by looking at actual values.
Then if it is true for $n=k$ and $n=k-1$ then $L_k=F_{k+1}+F_{k-1}$ and $L_{k-1}=F_{k}+F_{k-2}$ so $L_k+L_{k-1}=F_{k+1}+F_{k}+F_{k-1}+F_{k-2}$.
This means $L_{k+1}=F_{k+2}+F_{k}$, i.e. $L_n=F_{n+1}+F_{n-1}$ for $k=n+1$. And so you can use induction to claim it is true for all integer $n \ge 2$.