Recurrent Sequences: Key Results, Applications, and Problems

Description

This self-contained text presents state-of-the-art results on recurrent sequences and their applications in algebra, number theory, geometry of the complex plane and discrete mathematics. It is designed to appeal to a wide readership, ranging from scholars and academics, to undergraduate students, or advanced high school and college students training for competitions. The content of the book is very recent, and focuses on areas where significant research is currently taking place. Among the new approaches promoted in this book, the authors highlight the visualization of some recurrences in the complex plane, the concurrent use of algebraic, arithmetic, and trigonometric perspectives on classical number sequences, and links to many applications. It contains techniques which are fundamental in other areas of math and encourages further research on the topic. The introductory chapters only require good understanding of college algebra, complex numbers, analysis and basic combinatorics. For Chapters 3, 4 and 6 the prerequisites include number theory, linear algebra and complex analysis.   The first part of the book presents key theoretical elements required for a good understanding of the topic. The exposition moves on to to fundamental results and key examples of recurrences and their properties. The geometry of linear recurrences in the complex plane is presented in detail through numerous diagrams, which lead to often unexpected connections to combinatorics, number theory, integer sequences, and random number generation. The second part of the book presents a collection of 123 problems with full solutions, illustrating the wide range of topics where recurrent sequences can be found.  This material is ideal for consolidating the theoretical knowledge and for preparing students for Olympiads. Preface Overview and Goals Audience Organization and Features Prerequisites How to Use the Book Acknowledgements Contents 1 Introduction to Recurrence Relations 1.1 Recursive Sequences of Order k 1.2 Recurrent Sequences Defined by a Sequence of Functions 1.3 Systems of Recurrent Sequences 1.4 Existence and Uniqueness of the Solution 1.5 Recurrent Sequences Arising in Practical Problems 1.5.1 Applications in Mathematical Modeling 1.5.2 Algebra 1.5.3 Combinatorics 1.5.4 Geometry 1.5.5 Analysis 1.5.6 Iterative Numerical Methods 2 Basic Recurrent Sequences 2.1 First-Order Linear Recurrent Sequences 2.2 Second-Order Linear Recurrent Sequences 2.2.1 Homogeneous Recurrent Sequences 2.2.2 Nonhomogeneous Recurrent Sequences 2.2.3 Fibonacci, Lucas, Pell, and Pell–Lucas Numbers 2.2.4 The Polynomials Un(x,y) and Vn(x,y) 2.2.5 Properties of Fibonacci, Lucas, Pell, and Lucas–Pell Numbers 2.2.6 Zeckendorf's Theorem 2.3 Homographic Recurrences 2.3.1 Key Definitions 2.3.2 Homographic Recurrent Sequences 2.3.3 Representation Theorems for Homographic Sequences 2.3.4 Convergence and Periodicity 2.3.5 Homographic Recurrences with Variable Coefficients 3 Arithmetic and Trigonometric Properties of Some Classical Recurrent Sequences 3.1 Arithmetic Properties of Fibonacci and Lucas Sequences 3.2 Arithmetic Properties of Pell and Pell–Lucas Numbers 3.3 Trigonometric Expressions for the Fibonacci, Lucas, Pell, and Pell–Lucas Numbers 3.4 Identities Involving the Resultant of Polynomials 4 Generating Functions 4.1 Ordinary Generating Functions 4.1.1 Basic Operations and Examples 4.1.2 Generating Functions of Classical Polynomials 4.1.3 Generating Functions of Classical Sequences 4.1.4 The Explicit Formula for the Fibonacci, Lucas, Pell, and Pell–Lucas Polynomials 4.1.5 From Generating Functions to Propertiesof the Sequence 4.2 Exponential Generating Functions 4.2.1 Basic Operations and Examples 4.2.2 Generating Functions for Polynomials Un and Vn 4.2.3 Generating Functions of Classical Polynomials 4.2.4 Generating Functions of Classical Sequences 4.3 The Cauchy Integral Formula 4.3.1 A Useful Version of the Cauchy Integral Formula 4.3.2 The Integral Representation of Classical Sequences 5 More on Second-Order Linear Recurrent Sequences 5.1 Preliminary results 5.1.1 General Sequence Term 5.1.1.1 Nondegenerate Case: Distinct Roots (z1≠z2) 5.1.1.2 Degenerate Case: Equal Roots (z1=z2) 5.1.2 Ratios of Horadam Sequences 5.1.3 Particular Horadam Orbits 5.1.3.1 Orbits Produced by Conjugate Generators (if a,bR) 5.1.3.2 Concentric Orbits Produced by Opposite Entries 5.1.3.3 Conjugate Orbits Produced by Conjugate Parameters 5.2 Periodicity of Complex Horadam Sequences 5.2.1 Geometric Progressions of Complex Argument 5.2.2 Nondegenerate Case 5.2.3 Degenerate Case 5.3 The Geometry of Periodic Horadam Orbits 5.3.1 Regular Star Polygons 5.3.2 Bipartite Graphs 5.3.3 Multipartite Graphs 5.3.4 Geometric Bounds of Periodic Orbits 5.3.5 ``Masked'' Periodicity 5.4 The Enumeration of Periodic Horadam Patterns 5.4.1 The Number of Horadam Patterns of Fixed Length 5.4.1.1 Degenerate Orbits 5.4.1.2 Nondegenerate Orbits 5.4.2 A First Formula 5.4.3 A Second Formula 5.4.4 Computational Complexity 5.4.5 Asymptotic Bounds 5.5 Non-periodic Horadam Orbits 5.5.1 Degenerate Orbits 5.5.1.1 Behavior of Sequence (zn)n≥0 5.5.1.2 Patterns Produced by Identical Generators 5.6 An Atlas of Horadam Patterns 5.6.1 Stable Orbits: r1=r2=1 5.6.1.1 (a) Stable Periodic (Finite) Orbits 5.6.1.2 (b) Stable Orbits Dense Within 1D Curves 5.6.1.3 (c1) Orbits Dense Within Concentric Circles 5.6.1.4 (c2) Orbits Dense Within Closed 1D Curves 5.6.1.5 (c3) Stable Orbits Dense Within 2D Annuli 5.6.2 Quasi-Convergent Orbits for 0≤r1