2020/09/16 by Thomas C. Martinez, Martinez, Thomas C., Steven J. Miller +7
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2009.07891
openalex publication_date 2020/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Zeckendorf's theorem states that every positive integer can be written uniquely as the sum of non-consecutive shifted Fibonacci numbers \Fn\, where we take F1=1 and F2=2. This has been generalized for any Positive Linear Recurrence Sequence (PLRS), which informally is a sequence satisfying a homogeneous linear recurrence with a positive leading coefficient and non-negative integer coefficients. In this and the preceding paper we provide two approaches to investigate linear recurrences with leading coefficient zero, followed by non-negative integer coefficients, with differences between indices relatively prime (abbreviated ZLRR), via two different approaches. The first approach involves generalizing the definition of a legal decomposition for a PLRS found in Koloğlu, Kopp, Miller and Wang. We prove that every positive integer N has a legal decomposition for any ZLRR using the greedy algorithm. We also show that a specific family of ZLRRs lost uniqueness of decompositions. The second approach converts a ZLRR to a PLRR that has the same growth rate. We develop the Zeroing Algorithm, a powerful helper tool for analyzing the behavior of linear recurrence sequences. We use it to prove a very general result that guarantees the possibility of conversion between certain recurrences, and develop a method to quickly determine whether a sequence diverges to +∞ or -∞, given any real initial values. This paper investigates the second approach.