Originally Posted by
dannyboycurtis Hi I am having trouble completing an inductive proof to show that
where F is a Fibonacci number and L is a Lucas number.
The farthest I have gotten is:
I am stuck on how to show that
Any suggestions?
I am not sure what you know, so I will do a few lemmas for you.
Problem: Let denote the th Fibonacci and Lucas number respectively. Prove that
Proof:
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
and
.
Therefore,
This completes the induction.
Using this lemma we can easily prove that
and
.
Lemma: .
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
.
Similarly,
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