On the Asymptotic Behavior of Variance of PLRS Decompositions

A positive linear recurrence sequence is of the form Hn+1 = c1Hn + · · · + cLHn+1−L with each ci ≥ 0 and c1cL > 0, with appropriately chosen initial conditions. There is a notion of a legal decomposition (roughly, given a sum of terms in the sequence we cannot use the recurrence relation to reduce it) such that every positive integer has a unique legal decomposition using terms in the sequence; this generalizes the Zeckendorf decomposition, which states any positive integer can be written uniquely as a sum of non-adjacent Fibonacci numbers. Previous work proved not only that a decomposition exists, but that the number of summands Kn(m) in legal decompositions of m ∈ [Hn, Hn+1) converges to a Gaussian. Using partial fractions and generating functions it is easy to show the mean and variance grow linearly in n: an + b + o(1) and Cn + d + o(1), respectively; the difficulty is proving a and C are positive. Previous approaches relied on delicate analysis of polynomials related to the generating functions and characteristic polynomials, and is algebraically cumbersome. We introduce new, elementary techniques that bypass these issues. The key insight is to use induction and bootstrap bounds through conditional probability expansions to show the variance is unbounded, and hence C > 0 (the mean is handled easily through a simple counting argument).

In collections

File details
ID Label Size Mimetype Created
OBJ OBJ datastream 311.51 KiB application/pdf 2020-06-15
TN TN 2.45 KiB image/jpeg 2020-06-15