On the number of summands in Zeckendorf decompositions

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/({\phi }^2+1)+O(1)$, where $\phi =\frac{1+\sqrt{5}}{2}$ 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 $n\to \infty$. 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.

20 pages, 1 figure

Cited by in corpus (12)

• The Average Gap Distribution for Generalized Zeckendorf Decompositions
• New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
• Legal Decompositions Arising from Non-positive Linear Recurrences
• Gaussian Behavior of the Number of Summands in Zeckendorf Decompositions in Small Intervals
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
• Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II
• Extending Zeckendorf's Theorem to a Non-constant Recurrence and the Zeckendorf Game on this Non-constant Recurrence Relation
• Gaussian Distribution of the Number of Summands in Generalized Zeckendorf Decompositions in Small Intervals
• The Generalized Bergman Game
• On the Combinatorics of Placing Balls into Ordered Bins
• On the Asymptotic Behavior of Variance of PLRS Decompositions
• Difference in the Number of Summands in the Zeckendorf Partitions of Consecutive Integers