Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2.

Question

Fibonacci numbers F₁, F₂, F₃, . . . are defined by the rule: F₁ = F₂ = 1 and F_k = F_k−2 + F_k−1 for k > 2.

Lucas numbers L₁, L₂, L₃, . . . are defined in a similar way by the rule: L₁ = 1, L₂ = 3 and L_k = L_k−2 + L_k−1 for k > 2.

Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2

L_n = F_n−1 + F_n+1.

How would I go about doing this?

Answer 1

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.

Answer 2

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?