Completeness of Positive Linear Recurrence Sequences

DOI10.1007/978-3-031-10796-2_2MaRDI QIDQ6350505arXivFDO

Authors Elżbieta Bołdyriew, John Haviland, Phúc Lâm, John Lentfer, Steven J. Miller, Fernando Trejos Surez

Publication date 4 October 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-031-10796-2_2

Mathematics Subject Classification ID

Recurrences (11B37) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

arXiv classification

math.CO

Abstract: A sequence of positive integers is complete if every positive integer is a sum of distinct terms. A positive linear recurrence sequence (PLRS) is a sequence defined by a homogeneous linear recurrence relation with nonnegative coefficients of the form

H_{n + 1} = c_{1} H_{n} + c d o t s + c_{L} H_{n - L + 1}

and a particular set of initial conditions. We seek to classify various PLRS's by completeness. With results on how completeness is affected by modifying the recurrence coefficients of a PLRS, we completely characterize completeness of several families of PLRS's as well as conjecturing criteria for more general families. Our primary method is applying Brown's criterion, which says that an increasing sequence

{H_{n}}_{n = 1}^{i n f t y}

is complete if and only if

H_{1} = 1

and

H_{n + 1} l e q 1 + s u m_{i = 1}^{n} H_{i}

. %A survey of these results can be found in cite{BHLLMT}. Finally, we adopt previous analytic work on PLRS's to find a more efficient way to check completeness. Specifically, the characteristic polynomial of any PLRS has exactly one positive root; by bounding the size of this root, the majority of sequences may be classified as complete or incomplete. Additionally, we show there exists an indeterminate region where the principal root does not reveal any information on completeness. We have conjectured precise bounds for this region.

This page was built for publication: Completeness of Positive Linear Recurrence Sequences

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