Lucas chain

From Wikipedia, the free encyclopedia

In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Edouard Lucas. It is a sequence

a₀, a₁, a₂, a₃, ...

that satisfies

a₀=1,

and

for each k > 0: a_k = a_i + a_j, and either a_i = a_j or |a_i − a_j| = a_m, for some i, j, m < k.

The sequence of powers of 2 (1, 2, 4, 8, 16, ...) and the Fibonacci sequence (with a slight adjustment of the starting point 1, 2, 3, 5, 8, ...) are simple examples of Lucas chains.