Second-Order Lucas Sequences (Guy's Parametrization)
This page describes a certain class of integer sequences that are divisibility sequences and can be defined by a recurrence relation.
Contents
Introduction
The famous Fibonacci numbers (A0045 in OEIS) have two properties which are also seen in many other integer sequences:
- They are a divisibility sequence, meaning that for any two positive integers i and j, if i is divisible by j then sequence term Ai is divisible by sequence term Aj,
- They obey a recurrence relation, meaning that each term can be computed from the previous terms using an equation that uses only the previous terms as variables, and remains the same for all terms.
Second-Order Lucas Sequences
Edouard Lucas studied the two most well-known sequences of this type, the Fibonacci numbers and the Lucas numbers. Rather than giving the normal definitions, I'll use the generalized form which includes the parameters P and Q:
Fibonacci numbers:
A0=0; A1=1; An = P An-1 - Q An-2
(where P=1 and Q=-1)
Lucas numbers:
A0=2; A1=P; An = P An-1 - Q An-2
(where P=1 and Q=-1)
As you can see, the equation is An = PAn-1 - QAn-2 for both sequences, and the parameters P and Q are the same as well. The values P=1 and Q=-1 mean that the equation is the familiar An = An-1 + An-2.
Both of these definitions are a subset of the more general class of recurrence relations called the Horadam sequences.
For example, there are no fewer than five recurring sequences with characteristic polynomial
x4 - 40x3 + 206x2 - 40x + 1, which have initial values
(1), 0, 1, 48, ... (-1), 0, 1, 6, ... (-1), 0, 1, 30, ... (-1), 0, 1, 34, ... (-1), 0, 1, 48, ...
and are divisibility sequences.
(-1), 0, 1, 20, 595, 19720, 667029, 22642620, 769085031, 26125682960, 887500839785, ...
595 = 5×7×17,
19720 = 2^3×5×17×29,
667029 = 3×11×17×29×41,
22642620 = 2^2×3×5×7×11×13^2×29,
769085031 = 3×11×13^2×239×577,
26125682960 = 2^4×5×13^2×17×197×577,
887500839785 = 5×7×19×59×197×199×577
|
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2013 Feb 07. s.27