On the number of summands in Zeckendorf decompositions

MaRDI QIDQ3000475zbMATHFDO

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

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)

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

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)