Lucas Sequence

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.