Generalizing Zeckendorf's theorem to f-decompositions

DOI10.1016/J.JNT.2014.01.028MaRDI QIDQ402633zbMATHOpenAlexFDO

Authors Philippe Demontigny, Archit Kulkarni, Steven J. Miller, David Moon, Umang Varma, Thao Do

Publication date 28 August 2014

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5599

zbMATH Keywords

recurrence relationsStirling numbers of the first kindZeckendorf decompositionsGaussian behavior

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Bell and Stirling numbers (11B73) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

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 $min[G_n,G_{n+1})$ converges to a normal distribution as $noinfty$. 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:N_{0}o{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:N_{0}o{N}_0$, there exists a sequence ${a_n}_{n=0}^{i}nfty$ 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.

Recommendations

• New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
• Generalizing Zeckendorf's Theorem: The Kentucky Sequence
• A generalization of Zeckendorf's theorem via circumscribed \(m\)-gons
• Gaps of summands of the Zeckendorf lattice
• Legal decompositions arising from non-positive linear recurrences

Cites work

• scientific article; zbMATH DE number 4060392 (Why is no real title available?)
• scientific article; zbMATH DE number 1896939 (Why is no real title available?)
• scientific article; zbMATH DE number 2099178 (Why is no real title available?)
• scientific article; zbMATH DE number 3277086 (Why is no real title available?)
• scientific article; zbMATH DE number 3373770 (Why is no real title available?)
• scientific article; zbMATH DE number 3378996 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 3076700 (Why is no real title available?)
• A counting based proof of the generalized Zeckendorf's theorem
• A generalization of a theorem of Lekkerkerker to Ostrowski's decomposition of natural numbers
• Contributions to digit expansions with respect to linear recurrences
• Corrigendum to ``Generalized Zeckendorf expansions
• Differences of multiple Fibonacci numbers
• From Fibonacci numbers to central limit type theorems
• Gaussian behavior in generalized Zeckendorf decompositions
• Gaussian limiting distributions for the number of components in combinatorial structures
• Generalized Zeckendorf expansions
• On the number of summands in Zeckendorf decompositions
• Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers
• The algebraic structure of linearly recursive sequences under Hadamard product
• The average gap distribution for generalized Zeckendorf decompositions
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• The distribution of the sum-of-digits function

Cited in

(21)

• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• Bin decompositions
• On generalized decomposition numbers and Fong's reductions
• Legal decompositions arising from non-positive linear recurrences
• Recurrence relations for \(S\)-legal index difference sequences
• On generalized Zeckendorf decompositions and generalized golden strings
• Zeckendorf's theorem using indices in an arithmetic progression
• A probabilistic approach to generalized Zeckendorf decompositions
• The accelerated Zeckendorf game
• scientific article; zbMATH DE number 7824067 (Why is no real title available?)
• scientific article; zbMATH DE number 7633022 (Why is no real title available?)
• Dilworth's decomposition theorem for posets in ZF
• Summand minimality and asymptotic convergence of generalized Zeckendorf decompositions
• The Fibonacci sequence and Schreier-Zeckendorf sets
• On Zeckendorf Related Partitions Using the Lucas Sequence
• Average number of Zeckendorf integers
• Zeckendorf representation of multiplicative inverses modulo a Fibonacci number
• A generalization of Zeckendorf's theorem via circumscribed \(m\)-gons
• On the asymptotic behavior of variance of PLRS decompositions
• scientific article; zbMATH DE number 7676365 (Why is no real title available?)
• Patterns in variations of the Fibonacci sequence

This page was built for publication: Generalizing Zeckendorf's theorem to \(f\)-decompositions

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