mdbtxt1
mdbtxt2
Proceed to Safety

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:

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


Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2013 Feb 07. s.27