# 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

 characteristic polynomial recurrence relation -x2 - x + 1 An = An-1 + An-2 linrec([-1,-1],[0,1]) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, ... A0045, MCS840 x2 - 6x + 1 An = 6An-1 - An-2 linrec([1,-6],[-1,0]) (-1), 0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, ... A1109, MCS27113 x2 - 34x + 1 An = 34An-1 - An-2 linrec([1,-34],[-1,0]) (-1), 0, 1, 34, 1155, 39236, 1332869, 45278310, 1538129671, 52251130504, ... A91761 x4 - 40x3 + 206x2 - 40x + 1 An = 40 An-1 - 206 An-2 + 40 An-3 - An-4 linrec([1,-40,206,-40],[-1,0,1,48]) (-1), 0, 1, 48, 1715, 58752, 1998709, 67914000, 2307174311, 78376578048, ... P=40, Q=1, R=204; D=776, E=36864, disc.=22198616064

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2018 Aug 27. s.11