Generalizing Zeckendorf's Theorem to f-decompositions

Abstract

A beautiful theorem of Zeckendorf states that every positive integer can be uniquely decomposed as a sum of non-consecutive Fibonacci numbers $\{F_n\}$, where $F_1=1$, $F_2=2$ and $F_{n+1}=F_n+F_{n-1}$. For general recurrences $\{G_n\}$ with non-negative coefficients, there is a notion of a legal decomposition which again leads to a unique representation, and the number of summands in the representations of uniformly randomly chosen $m\in [G_n,G_{n+1})$ converges to a normal distribution as $n\to \infty$. We consider the converse question: given a notion of legal decomposition, is it possible to construct a sequence $\{a_n\}$ such that every positive integer can be decomposed as a sum of terms from the sequence? We encode a notion of legal decomposition as a function $f:{\mathbb{N}}_0\to {\mathbb{N}}_0$ and say that if $a_n$ is in an "$f$-decomposition", then the decomposition cannot contain the $f(n)$ terms immediately before $a_n$ in the sequence; special choices of $f$ yield many well known decompositions (including base-$b$, Zeckendorf and factorial). We prove that for any $f:{\mathbb{N}}_0\to {\mathbb{N}}_0$, there exists a sequence $\{a_n{\}}_{n=0}^{\infty }$ such that every positive integer has a unique $f$-decomposition using $\{a_n\}$. Further, if $f$ is periodic, then the unique increasing sequence $\{a_n\}$ that corresponds to $f$ satisfies a linear recurrence relation. Previous research only handled recurrence relations with no negative coefficients. We find a function $f$ that yields a sequence that cannot be described by such a recurrence relation. Finally, for a class of functions $f$, we prove that the number of summands in the $f$-decomposition of integers between two consecutive terms of the sequence converges to a normal distribution.

Version 1.0, 18 pages, keywords: Zeckendorf decompositions, recurrence relations, Stirling numbers of the first kind, Gaussian behavior

References in corpus (2)

• The Average Gap Distribution for Generalized Zeckendorf Decompositions
• The Distribution of Gaps between Summands in Generalized Zeckendorf Decompositions

Cited by in corpus (21)

• 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
• A Generalization of Zeckendorf's Theorem via Circumscribed $m$-gons
• Gaussian Behavior in Zeckendorf Decompositions From Lattices
• Deterministic Zeckendorf Games
• Individual Gap Measures from Generalized Zeckendorf Decompositions
• Gaps of Summands of the Zeckendorf Lattice
• Central Limit Theorems for Compound Paths on the 2-Dimensional Lattice
• The Distribution of Gaps between Summands in Generalized Zeckendorf Decompositions
• Extending Zeckendorf's Theorem to a Non-constant Recurrence and the Zeckendorf Game on this Non-constant Recurrence Relation
• On Zeckendorf Related Partitions Using the Lucas Sequence
• On the Asymptotic Behavior of Variance of PLRS Decompositions
• Gaussian Distribution of the Number of Summands in Generalized Zeckendorf Decompositions in Small Intervals
• Bin Decompositions
• Limiting Distributions in Generalized Zeckendorf Decompositions
• Zeckendorf's Theorem Using Indices in an Arithmetic Progression
• The Fibonacci Sequence and Schreier-Zeckendorf Sets
• Difference in the Number of Summands in the Zeckendorf Partitions of Consecutive Integers