2014/09/01 by Andrew Best, Best, Andrew, Patrick Dynes +13 · 1 citation
Mathematics · Computer Science · Physics and Astronomy · #Advanced Combinatorial Mathematics #semigroups and automata theory #Advanced Mathematical Theories and Applications
paper · pdf · doi:10.48550/arxiv.1409.0483
Zeckendorf's theorem states that every positive integer can be written uniquely as a sum of non-consecutive Fibonacci numbers Fn, with initial terms F1 = 1, F2 = 2. We consider the distribution of the number of summands involved in such decompositions. Previous work proved that as n → ∞ the distribution of the number of summands in the Zeckendorf decompositions of m ∈ [Fn, Fn+1), appropriately normalized, converges to the standard normal. The proofs crucially used the fact that all integers in [Fn, Fn+1) share the same potential summands. We generalize these results to subintervals of [Fn, Fn+1) as n → ∞; the analysis is significantly more involved here as different integers have different sets of potential summands. Explicitly, fix an integer sequence α(n) → ∞. As n → ∞, for almost all m ∈ [Fn, Fn+1) the distribution of the number of summands in the Zeckendorf decompositions of integers in the subintervals [m, m + Fα(n)), appropriately normalized, converges to the standard normal. The proof follows by showing that, with probability tending to 1, m has at least one appropriately located large gap between indices in its decomposition. We then use a correspondence between this interval and [0, Fα(n)) to obtain the result, since the summands are known to have Gaussian behavior in the latter interval. % We also prove the same result for more general linear recurrences.