On the number of summands in Zeckendorf decompositions

zbMATH Open1225.11021arXiv1008.3204MaRDI QIDQ3000475FDOQ3000475

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

Publication date: 18 May 2011

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.

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

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

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)

Cited In (32)

• A generalization of Fibonacci far-difference representations and Gaussian behavior
• Gaussian behavior of the number of summands in Zeckendorf decompositions in small intervals
• Generalizing Zeckendorf's theorem to \(f\)-decompositions
• Benford behavior of Zeckendorf decompositions
• From Fibonacci numbers to central limit type theorems
• Title not available (Why is that?)
• On the sum of digits of the Zeckendorf representations of two consecutive numbers
• On the Combinatorics of Placing Balls into Ordered Bins
• Title not available (Why is that?)
• The number of subsets of the set \([n]\) containing no two consecutive even integers
• On generalized Zeckendorf decompositions and generalized golden strings
• The average gap distribution for generalized Zeckendorf decompositions
• Gaussian behavior in generalized Zeckendorf decompositions
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• On the average number of summands in the Zeckendorf representation
• Decompositions of zonoids
• The Zeckendorf representation of a Beatty-related Fibonacci sum
• Title not available (Why is that?)
• The Fibonacci sequence and Schreier-Zeckendorf sets
• When almost all sets are difference dominated in \(\mathbb{Z}/n\mathbb{Z}\)
• Title not available (Why is that?)
• The weak converse of Zeckendorf's theorem
• 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
• Title not available (Why is that?)
• 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)