Recurrent Sequences

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 1
	6.7 Connection to Finite Differences
		6.7.1 Solving Difference Equations
		6.7.2 Finding the Difference Equation for a Sequence
7 Recurrences in Olympiad Training
	7.1 First-Order Recurrent Sequences
	7.2 Second-Order Recurrent Sequences
	7.3 Classical Recurrent Sequences
	7.4 Higher Order Recurrence Relations
	7.5 Systems of Recurrence Relations
	7.6 Homographic Recurrent Sequences
	7.7 Complex Recurrent Sequences
	7.8 Recurrent Sequences in Combinatorics
	7.9 Miscellaneous
8 Solutions to Proposed Problems
	8.1 First-Order Recurrent Sequences
	8.2 Second-Order Recurrent Sequences
	8.3 Classical Recurrent Sequences
	8.4 Higher Order Recurrent Sequences
	8.5 Systems of Recurrence Relations
	8.6 Homographic Recurrent Sequences
	8.7 Complex Recurrent Sequences
	8.8 Recurrent Sequences in Combinatorics
	8.9 Miscellaneous
Appendix
A Complex Geometry and Number Theory
	A.1 Complex Geometry
		A.1.1 The Triangle Inequality
		A.1.2 Regular Star Polygons and Multipartite Graphs
	A.2 Key Elements of Number Theory
		A.2.1 The lcm and gcd of Integer Pairs
		A.2.2 The lcm and gcd of Integer Tuples
		A.2.3 Links Between the lcm and gcd of Integer Tuples
		A.2.4 Euler's Totient Function
		A.2.5 The ``Stars and Bars'' Argument
		A.2.6 Partitions of Numbers and Stirling Numbers
		A.2.7 Linear (In)dependence and Density Results
	A.3 Numerical Implementation of LRS General Terms
		A.3.1 Distinct Roots
		A.3.2 Equal Roots
		A.3.3 Distinct Roots z1,…,zm of Higher Multiplicities d1,…, dm
References
References
Index