From Fibonacci Numbers to Central Limit Type Theorems

A beautiful theorem of Zeckendorf states that every integer can be written uniquely as a sum of non-consecutive Fibonacci numbers {Fn}∞n=1. Lekkerkerker [Lek] proved the average number of summands for integers in [Fn, Fn+1) is n/(φ 2+1), with φ the golden mean. This has been generalized: given nonnegative integers c1, c2,..., cL with c1, cL> 0 and recursive sequence {Hn}∞n=1 withH1 = 1, Hn+1 = c1Hn+ c2Hn−1+ · · ·+ cnH1+1 (1 ≤ n < L) and Hn+1 = c1Hn+ c2Hn−1+ · · ·+ cLHn+1−L (n ≥ L), every positive integer can be written uniquely as ∑ aiHi under natural constraints on the ai’s, the mean and variance of the numbers of summands for integers in [Hn,Hn+1) are of size n, and as n→ ∞ the distribution of the number of summands converges to a Gaussian. Previous approaches used number theory or ergodic theory. We convert the problem to a combinatorial one. In addition to re-deriving these results, our method generalizes to other problems (in the sequel paper [BGM] we show how this perspective allows us to determine the distribution of gaps between summands). For example, it is known that every integer can be written uniquely as a sum of the ±Fn’s, such that every two terms of the same (opposite) sign differ in index by at least 4 (3). The presence of negative summands introduces complications and features not seen in previous problems. We prove that the distribution of the numbers of positive and negative summands converges to a bivariate normal with computable, negative correlation, namely −(21 − 2φ)/(29 + 2φ) ≈ −0.551058. 1