Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II

Authors Thomas C. Martinez, Steven J. Miller, Clayton M. Mizgerd, Chenyang Sun

Publication date 16 September 2020

Other number representations (11A67) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: Zeckendorf's theorem states that every positive integer can be written uniquely as the sum of non-consecutive shifted Fibonacci numbers

F_{n}

, where we take

F_{1} = 1

and

F_{2} = 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 Kolou{g}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

+ i n f t y

or

- i n f t y

, given any real initial values. This paper investigates the second approach.

This page was built for publication: Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349263)