The Lucas Sequences. Theory and Applications

The Lucas Sequences. Theory and Applications

By Christian J.-C. Ballot and Hugh C. Williams
CMS/CAIMS Books in Mathematics, Springer 2023
Reviewed by Karl Dilcher

The fact that the celebrated numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, … are now known as Fibonacci numbers is mainly due to Édouard Lucas (1842-1891). Leonardo of Pisa (aka Fibonacci) lived in the decades around 1200, but soon he and his work were largely forgotten for centuries. Only much later, in 1844, the numbers now bearing Leonardo’s name were rediscovered by Gabriel Lamé in connection with his analysis of the Euclidean algorithm, and they were first known to Lucas as the Lamé sequence. However, as is often the case with mathematical objects named after persons, the Fibonacci numbers had been discovered earlier, and were already known by Indian mathematicians long before Leonardo. These are just some of the interesting historical remarks that can be found in the introduction (and elsewhere) in the book under review.

To introduce the main topic of this book, we recall that the Fibonacci numbers F_n are usually defined recursively by F₀ = 0, F₁ = 1, and F_n+1= F_n + F_n-1 (n ≥ 1). Their companion sequence, the Lucas numbers (not to be confused with the Lucas sequences) are similarly defined by L₀ = 2, L₁ = 1, and L_n+1 = L_n + L_n-1 (n ≥ 1). Now, given two nonzero integers P and Q, one defines the fundamental Lucas sequence U_n= U_n(P,Q) and the companion (or associate) Lucas sequence V_n = V_n(P,Q) by

U₀ = 0, U₁ = 1,  and  U_n+1= PU_n – QU_n-1  (n ≥ 1),

V₀ = 2, V₁ = P,  and  V_n+1= PV_n – QV_n-1  (n ≥ 1),

respectively. Clearly, when P = 1 and Q = -1, these two sequences reduce to the Fibonacci and Lucas numbers, respectively. Nearly all known properties of these two special sequences extend to the Lucas sequences and their companion sequences. One of the main goals of the book under review is to collect the most important of these properties and identities, and to present a coherent theory. To quote from the Introduction,

“The objective of this book is to provide a much more thorough discussion of the Lucas sequences than is available in existing monographs. We will bring together a variety of results, which are currently scattered throughout the literature. Various sections will be devoted to intrinsic arithmetic properties of these sequences, primality testing, density problems, and the problem of generalizing them. Furthermore, their application, not only to primality testing but to integer factoring, solution of quadratic and cubic congruences, cryptography, and Diophantine equations, will be briefly discussed. Throughout the book, we will include a sprinkling of historical comments, where relevant.

“Much of the book is not intended to be overly detailed. Rather, our objective is to provide a good, elementary, and clear explanation of the subject matter without too much ancillary material. Most chapters […] will address a particular theme, provide enough information for the reader to get a feel for the subject, and supply references to more comprehensive results. We have also attempted to make this book accessible to anyone with a basic knowledge of elementary number theory and abstract algebra.

“Our intended audience is number theorists, both professional and amateur, students, and enthusiasts. We emphasize that this book was never intended to be a textbook; its focus is either much too narrow or too broad for that, but it might be used as supplementary reading for students enrolled in second or more advanced courses in number theory.”

In my opinion, the authors succeeded very well in their stated objectives and intentions. The book is written in a lively style and is a pleasure to read. The various chapters are, to a certain extent, self-contained, with their own abstracts and lists of references. After the Introduction, Chapter 2 contains the basic theory of the Lucas sequences. Chapter 3, entitled “Applications”, begins with a discussion of the Mersenne numbers and continues with applications to primality testing, solving certain congruences, integer factorization, and other applications. Chapter 4 deals with further properties and contains connections with the circular functions, Chebyshev polynomials, and the Dickson polynomials. Chapter 5 is a detailed study of the Lucasnomial coefficients, a generalization of the usual binomial coefficients. The next three chapters, “Cubic Extensions of the Lucas Sequences”, “Linear Recurrence Sequences and Further Generalizations”, and “Divisibility Sequences and Further Generalizations” deal with various generalizations of Lucas Sequences, including Lucas’s own ideas and results. Chapter 9 is of a somewhat different nature and deals with prime densities. The final chapter contains a brief epilogue summarizing the material covered and ends with a selection of 13 unsolved problems (one of which is already solved, as the authors mention in a note added to the problem).

The final paragraph of the book’s epilogue is worth quoting here: “We have seen, then, that much has been learned about the Lucas sequences since the end of the nineteenth century. Indeed, it seems remarkable that such a large amount of activity has been devoted to such a simple pair of sequences, but still there seems to be much more to do. A glance at publications such as the Journal of Integer Sequences, the Fibonacci Quarterly, Integers, and the Online Encyclopedia of Integers Sequences (OEIS) suggests that interest in these sequences shows no sign of diminishing.”

The main content of the book is followed by an appendix with a biographical sketch of Lucas, whose life was tragically cut short as a result of a freak accident he suffered at age 49. This appendix also contains comments on his work and scientific legacy.

This excellent book by Ballot and Williams will lead the interested reader through the vast amount of relevant literature and the numerous related topics. I am sure it will prove to be as useful and important as some other classic books with similar scopes, for instance T. J. Rivlin’s Chebyshev Polynomials (Wiley, 1990), Richard Stanley’s Catalan Numbers (Cambridge, 2015), and two well-known books mainly devoted to Fibonacci and Lucas numbers, by T. Koshy (Wiley, 2018) and by S. Vajda (Dover, 2008).

Finally, it should be mentioned that this book is the latest of three related monographs authored or co-authored by H. C. Williams, the other two being Édouard Lucas and Primality Testing (CMS Monographs, Wiley, 1998) and Solving the Pell Equation, with M. J. Jacobson, Jr. (CMS Books in Mathematics, Springer, 2009).