Question

The lucas numbers are given by the recurrence ln = ln-1 + ln-2 with boundary conditions l0 = 2, l1 = 1. show that ln = fn-1 + fn+1 for n ≥ 2, where fn is the nth fibonacci number.

Answer 1

1) Given:

Lucas number:


`L _(0) =2 L_(1) =1 L_(n)=L_(n-1)+L_(n-2)`

2) Fibonacci number:

Definition from any book or internet


`F_(0)=0 F_(1)=1 F_(n)=F_(n-1)+F_(n-2)`

3) Table

n Lucas number Fibonacci number

0 Lo = 2 Fo = 0

1 L1 = 1 F1 = 1

2 L2 = 1 + 2 = 3 F2 = 1 + 0 = 1 ⇒ L2 = F1 + F3 = 1 + 2 = 3

3 L3 = 3 + 1 = 4 F3 = 1 + 1 = 2 ⇒ L3 = F2 + F4 = 1 + 3 = 4

4 L4 = 4 + 3 = 7 F4 = 1 + 2 = 3 ⇒ L4 = F3 + F5 = 2 + 5 = 7

5) L5 = 7 + 4 = 11 F5 = 4 + 3 = 5 ⇒ L5 = F4 + F6 = 3 + 8 = 11

6) L6 = 11 + 7 = 18 F6 = 3 + 7 = 10 ⇒ L6 = F5 + F7 = 5 + 13 = 18

From that you can see that the relation continues.