On the number of summands in Zeckendorf decompositions

MaRDI QIDQ3000475zbMATH OpenFDO

Authors Murat Koloğlu, Gene S. Kopp, Steven J. Miller, Yinghui Wang

Publication date 18 May 2011

Full work available at URL https://arxiv.org/abs/1008.3204, http://www.fq.math.ca/Abstracts/49-2/kologlu.pdf

zbMATH Keywords

asymptotic distributionFibonacci numbersGaussian

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Numerical aspects of recurrence relations (65Q30)

Abstract: Zeckendorf proved that every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers. Once this has been shown, it's natural to ask how many summands are needed. Using a continued fraction approach, Lekkerkerker proved that the average number of such summands needed for integers in $[F_n,F_{n+1})$ is $n/(varph{i}^2+1)+O(1)$, where $varphi=frac1+sqrt52$ is the golden mean. Surprisingly, no one appears to have investigated the distribution of the number of summands; our main result is that this converges to a Gaussian as $noinfty$. Moreover, such a result holds not just for the Fibonacci numbers but many other problems, such as linear recurrence relation with non-negative integer coefficients (which is a generalization of base $B$ expansions of numbers) and far-difference representations. In general the proofs involve adopting a combinatorial viewpoint and analyzing the resulting generating functions through partial fraction expansions and differentiating identities. The resulting arguments become quite technical; the purpose of this paper is to concentrate on the special and most interesting case of the Fibonacci numbers, where the obstructions vanish and the proofs follow from some combinatorics and Stirling's formula; see [MW] for proofs in the general case.

Recommendations

• Gaussian behavior in generalized Zeckendorf decompositions
• From Fibonacci numbers to central limit type theorems
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• Gaussian behavior of the number of summands in Zeckendorf decompositions in small intervals
• The average gap distribution for generalized Zeckendorf decompositions

Cited in

(34)

• Generalizing Zeckendorf's theorem to \(f\)-decompositions
• A generalization of Fibonacci far-difference representations and Gaussian behavior
• From Fibonacci numbers to central limit type theorems
• Gaussian behavior of the number of summands in Zeckendorf decompositions in small intervals
• Benford behavior of Zeckendorf decompositions
• scientific article; zbMATH DE number 1222518 (Why is no real title available?)
• On the sum of digits of the Zeckendorf representations of two consecutive numbers
• On the Combinatorics of Placing Balls into Ordered Bins
• scientific article; zbMATH DE number 6017832 (Why is no real title available?)
• The number of subsets of the set \([n]\) containing no two consecutive even integers
• On generalized Zeckendorf decompositions and generalized golden strings
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• The average gap distribution for generalized Zeckendorf decompositions
• Gaussian behavior in generalized Zeckendorf decompositions
• On the average number of summands in the Zeckendorf representation
• Decompositions of zonoids
• The Zeckendorf representation of a Beatty-related Fibonacci sum
• scientific article; zbMATH DE number 7824067 (Why is no real title available?)
• The Fibonacci sequence and Schreier-Zeckendorf sets
• scientific article; zbMATH DE number 3972948 (Why is no real title available?)
• When almost all sets are difference dominated in \(\mathbb{Z}/n\mathbb{Z}\)
• The weak converse of Zeckendorf's theorem
• Some properties of Fibonacci numbers using center of mass
• A probabilistic approach to generalized Zeckendorf decompositions
• Some combinatorics from Zeckendorf representations
• A generalization of a theorem of Lekkerkerker to Ostrowski's decomposition of natural numbers
• The accelerated Zeckendorf game
• scientific article; zbMATH DE number 1391717 (Why is no real title available?)
• On the variation of the sum of digits in the Zeckendorf representation: an algorithm to compute the distribution and mixing properties
• Unique representations of integers using increasing sequences
• On Zeckendorf Related Partitions Using the Lucas Sequence
• Average number of Zeckendorf integers
• Combinatorial constructions for the Zeckendorf sum of digits of polynomial values
• On Zeckendorf and base \(b\) digit sums

This page was built for publication: On the number of summands in Zeckendorf decompositions

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