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.

1) Given:

Lucas number:

[tex]L _{0} =2 L_{1} =1 L_{n}=L_{n-1}+L_{n-2}[/tex]

2) Fibonacci number:

Definition from any book or internet

[tex]F_{0}=0 F_{1}=1 F_{n}=F_{n-1}+F_{n-2}[/tex]

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.