I am not sure what you know, so I will do a few lemmas for you.
Originally Posted by dannyboycurtis
Problem: Let denote the th Fibonacci and Lucas number respectively. Prove that
Lemma: Let be a second order homogenous linear recurrence relation. Also, suppose the charctersitic polynomial has real solutions . Then where .
Proof: We do this by strong induction induction.
Base case: .
Inductive hypothesis: Assume that for all
Inductive step: . From here a little manipulation yields . Remembering though that
are both solutions to we see that
This completes the induction.
Using this lemma we can easily prove that
Proof: Just note that
Grouping the terms and factoring out common stuff gives
Realizing though that
are solutions to
, we may shorten our calculations a bit and see that
Utilizing this we may finally see that
The conclusion follows.
This should help with your induction.
Remark: In fact, to end the proof without induction merely note that:
And using the difference of squares identity we see that