Generalizing Zeckendorf's theorem to f-decompositions

DOI10.1016/J.JNT.2014.01.028zbMATH Open1309.11013arXiv1309.5599OpenAlexW2011494645MaRDI QIDQ402633FDOQ402633

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

Publication date: 28 August 2014

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Gaussian limiting distributions for the number of components in combinatorial structures
• Title not available (Why is that?)
• Contributions to digit expansions with respect to linear recurrences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized Zeckendorf expansions
• The distribution of the sum-of-digits function
• Corrigendum to ``Generalized Zeckendorf expansions
• A generalization of a theorem of Lekkerkerker to Ostrowski's decomposition of natural numbers
• On the number of summands in Zeckendorf decompositions
• Differences of multiple Fibonacci numbers
• From Fibonacci numbers to central limit type theorems
• Title not available (Why is that?)
• The distribution of gaps between summands in generalized Zeckendorf decompositions
• Gaussian Behavior in Generalized Zeckendorf Decompositions
• The Average Gap Distribution for Generalized Zeckendorf Decompositions
• A counting based proof of the generalized Zeckendorf's theorem
• Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• The algebraic structure of linearly recursive sequences under Hadamard product

Cited In (15)

• The distribution of gaps between summands in generalized Zeckendorf decompositions
• Bin decompositions
• The Fibonacci Sequence and Schreier-Zeckendorf Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A probabilistic approach to generalized Zeckendorf decompositions
• Title not available (Why is that?)
• The accelerated Zeckendorf game
• Patterns in variations of the Fibonacci sequence
• On generalized decomposition numbers and Fong's reductions
• On Zeckendorf Related Partitions Using the Lucas Sequence
• Zeckendorf representation of multiplicative inverses modulo a Fibonacci number
• Average number of Zeckendorf integers
• Dilworth's decomposition theorem for posets in ZF

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)