The Average Gap Distribution for Generalized Zeckendorf Decompositions

Abstract

An interesting characterization of the Fibonacci numbers is that, if we write them as $F_1=1$, $F_2=2$, $F_3=3$, $F_4=5,...$, then every positive integer can be written uniquely as a sum of non-adjacent Fibonacci numbers. This is now known as Zeckendorf's theorem [21], and similar decompositions exist for many other sequences $G_{n+1}=c_1{G}_n+...+c_L{G}_{n+1-L}$ arising from recurrence relations. Much more is known. Using continued fraction approaches, Lekkerkerker [15] proved the average number of summands needed for integers in $[G_n,G_{n+1})$ is on the order of $C_{\mathrm{Lek}}n$ for a non-zero constant; this was improved by others to show the number of summands has Gaussian fluctuations about this mean. Kolo$\breve{\mathrm{g}}$lu, Kopp, Miller and Wang [17, 18] recently recast the problem combinatorially, reproving and generalizing these results. We use this new perspective to investigate the distribution of gaps between summands. We explore the average behavior over all $m\in [G_n,G_{n+1})$ for special choices of the $c_i$'s. Specifically, we study the case where each $c_i\in 0,1$ and there is a $g$ such that there are always exactly $g-1$ zeros between two non-zero $c_i$'s; note this includes the Fibonacci, Tribonacci and many other important special cases. We prove there are no gaps of length less than $g$, and the probability of a gap of length $j>g$ decays geometrically, with the decay ratio equal to the largest root of the recurrence relation. These methods are combinatorial and apply to related problems; we end with a discussion of similar results for far-difference (i.e., signed) decompositions.

15 pages, version 2.1, final version (fixed a typo in a combinatorial identity) -- to appear in the Fibonacci Quarterly

References in corpus (1)

• On the number of summands in Zeckendorf decompositions

Cited by in corpus (16)

• Generalizing Zeckendorf's Theorem to f-decompositions
• New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
• Legal Decompositions Arising from Non-positive Linear Recurrences
• Gaussian Behavior of the Number of Summands in Zeckendorf Decompositions in Small Intervals
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
• Summand minimality and asymptotic convergence of generalized Zeckendorf decompositions
• Gaps of Summands of the Zeckendorf Lattice
• Individual Gap Measures from Generalized Zeckendorf Decompositions
• An Introduction to Completeness of Positive Linear Recurrence Sequences
• Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II
• Central Limit Theorems for Compound Paths on the 2-Dimensional Lattice
• Extending Zeckendorf's Theorem to a Non-constant Recurrence and the Zeckendorf Game on this Non-constant Recurrence Relation
• The Distribution of Gaps between Summands in Generalized Zeckendorf Decompositions
• Gaussian Distribution of the Number of Summands in Generalized Zeckendorf Decompositions in Small Intervals
• Limiting Distributions in Generalized Zeckendorf Decompositions
• The Fibonacci Sequence and Schreier-Zeckendorf Sets