Integer Sequences: Divisibility, Lucas and Lehmer Sequences

Masum Billal and Samin Riasat

Publisher:

Springer

Publication Date:

2021

Number of Pages:

181

Format:

Hardcover

Price:

119.99

ISBN:

978-981-16-0569-7

Category:

Monograph

MAA Review
Table of Contents

[Reviewed by

Allen Stenger

, on

09/20/2021

]

There are many, many facts and properties known about the sequence of Fibonacci numbers \( F_{n} \) , and there is a whole industry devoted to discovering and publicizing these facts. The present book abstracts some of these properties and studies them in general integer sequences. The book is inspired by the work of the late Caltech mathematician Morgan Ward (1901–1963).

For example, one simple but surprising fact is that if \( m | n \) then \( F_{m} | F_{n} \) (the notation \( m | n \) means that m divides n, in other words that \( n/m \) is an integer). Generalizing, we say that an integer sequence \( a_{n} \) is a divisibility sequence if whenever \( m | n \) we have \( a_{m}| a_{n} \) , and divisibility sequences are studied in Chapter 3 of the present book.

The book is primarily interested in sequences that satisfy a linear recurrence, that is, sequences \( a_{n} \) satisfying

\( a_{n+k} = c_{k−1} a_{n+k−1} + \ldots. + c_{1} a_{n+1} + c_{0} a_{n} + \alpha \).

Usually the \( a_{n} \), \( c_{k} \), and \( \alpha \) are considered to be integers, but in some cases (especially Chapter 2) we’ll take them all to be elements of a finite field. For example, the Fibonacci numbers satisfy the linear recurrence \( F_{n+2}=F_{n+1} + F_{n} \).

The prerequisites for the book are low. It assumes some elementary number theory and a little bit of abstract algebra. Chapter 1 summarizes most of the background needed.

Chapter 2 deals with sequences that are eventually periodic, and investigates theorems about the length of the period and the length of the sequence before the period starts (called here the pre-period). Usually, we are dealing with sequences in a finite field, but there is also some discussion of periodic integer sequences. Chapter 3 (as mentioned above) deals with divisibility sequences.

Chapters 4 and 5 deal with Lucas and Lehmer sequences, respectively. Lucas sequences generalize the Fibonacci sequence by considering a recurrence \( L_{n}=aL_{n-1}-bL_{n-2} \) where \( a \) and \( b \) are integers. Lehmer sequences generalize Lucas sequences by considering the same recurrence except that we take \( a= \sqrt{c} \) where \( c \) is an integer; this is a case where the coefficients of the recurrence are not all integers. Chapter 6 deals with primitive prime divisors of a sequence. Primitive in this context means first, so we investigate the first index \( n \) for which a given prime divides \( a_{n} \) .

Chapter 7 contains exercises, most with solutions. They are not closely related to the first six chapters, although they share some techniques. Most of them deal with divisibility properties of elements of a sequence; for example, Problem 7.14 asks for all positive integers \( n \) such that \( n^{2} | 2^{n}+1 \). Many others deal with solutions of Diophantine equations. Most of the problems originate in the International Mathematical Olympiad or the training for the IMO.

The book is weak on examples (except in the exercises). In particular, we almost never see specific numeric sequences, although the Fibonacci sequence is cited often. The book contains very little Fibonacci lore, because its focus is elsewhere. Good sources for this material are Vajda’s Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Vorobiev’s Fibonacci Numbers, and Koshy’s comprehensive Fibonacci and Lucas Numbers with Applications. There is also a specialized journal, Fibonacci Quarterly, that is very valuable.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His personal web site is allenstenger.com. His mathematical interests are number theory and classical analysis.

See the publisher's website.

Tags:

Fibonacci Numbers