Gaussian Behavior in Generalized Zeckendorf Decompositions

Abstract

A beautiful theorem of Zeckendorf states that every integer can be written uniquely as a sum of non-consecutive Fibonacci numbers $\{F_n{\}}_{n=1}^{\infty }$; Lekkerkerker proved that the average number of summands for integers in $[F_n,F_{n+1})$ is $n/({\varphi }^2+1)$, with $\varphi$ the golden mean. Interestingly, the higher moments seem to have been ignored. We discuss the proof that the distribution of the number of summands converges to a Gaussian as $n\to \infty$, and comment on generalizations to related decompositions. For example, every integer can be written uniquely as a sum of the $\pm F_n$'s, such that every two terms of the same (opposite) sign differ in index by at least 4 (3). The distribution of the numbers of positive and negative summands converges to a bivariate normal with computable, negative correlation, namely $-(21-2\varphi )/(29+2\varphi )\approx -0.551058$.

This is a survey article based on talks given at CANT 2010 and CANT 2011