Let , be integers satisfying
(1)
|
Then roots of
(2)
|
are
(3)
| |||
(4)
|
so
(5)
| |||
(6)
| |||
(7)
| |||
(8)
|
Now define
(9)
| |||
(10)
|
for integer , so the first few values are
(11)
| |||
(12)
| |||
(13)
| |||
(14)
| |||
(15)
| |||
(16)
| |||
(17)
| |||
(18)
| |||
(19)
| |||
(20)
| |||
(21)
|
and
(22)
| |||
(23)
| |||
(24)
| |||
(25)
| |||
(26)
| |||
(27)
| |||
(28)
| |||
(29)
| |||
(30)
| |||
(31)
| |||
(32)
|
Closed forms for these are given by
(33)
| |||
(34)
|
The sequences
(35)
| |||
(36)
|
are called Lucas sequences, where the definition is usually extended to include
(37)
|
The following table summarizes special cases of and .
Fibonacci numbers | Lucas numbers | |
Pell numbers | Pell-Lucas numbers | |
Jacobsthal numbers | Pell-Jacobsthal numbers |
The Lucas sequences satisfy the general recurrence relations
(38)
| |||
(39)
| |||
(40)
| |||
(41)
| |||
(42)
| |||
(43)
|
Taking then gives
(44)
| |||
(45)
|
Other identities include
(46)
| |||
(47)
| |||
(48)
| |||
(49)
| |||
(50)
|
These formulas allow calculations for large to be decomposed into a chain in which only four quantities must be kept track of at a time, and the number of steps needed is . The chain is particularly simple if has many 2s in its factorization.