Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, I

zbMATH Open1517.11005arXiv2001.08455MaRDI QIDQ6333364FDOQ6333364

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

Publication date: 23 January 2020

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. These decompositions are generalizations of base

B

decompositions. In this and the follow-up 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). 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 loses 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 certain sequences diverge to

+ i n f t y

or

- i n f t y

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

Mathematics Subject Classification ID

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

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

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