3
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ Induction on $n$. $\endgroup$ Oct 28, 2014 at 19:12

2 Answers 2

3
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What about using induction? How can we do it then? $\endgroup$
    – someguy234
    Nov 7, 2014 at 1:13
  • 1
    $\begingroup$ @ gurinderhans : Check out my second answer above. $\endgroup$
    – user144361
    Nov 9, 2014 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.