Benford Behavior of Generalized Zeckendorf Decompositions

Abstract

We prove connections between Zeckendorf decompositions and Benford's law. Recall that if we define the Fibonacci numbers by $F_1=1,F_2=2$ and $F_{n+1}=F_n+F_{n-1}$, every positive integer can be written uniquely as a sum of non-adjacent elements of this sequence; this is called the Zeckendorf decomposition, and similar unique decompositions exist for sequences arising from recurrence relations of the form $G_{n+1}=c_1{G}_n+\cdots +c_L{G}_{n+1-L}$ with $c_i$ positive and some other restrictions. Additionally, a set $S\subset \mathbb{Z}$ is said to satisfy Benford's law base 10 if the density of the elements in $S$ with leading digit $d$ is ${\log }_{10}(1+\frac{1}{d})$; in other words, smaller leading digits are more likely to occur. We prove that as $n\to \infty$ for a randomly selected integer $m$ in $[0,G_{n+1})$ the distribution of the leading digits of the summands in its generalized Zeckendorf decomposition converges to Benford's law almost surely. Our results hold more generally: one obtains similar theorems to those regarding the distribution of leading digits when considering how often values in sets with density are attained in the summands in the decompositions.

11 pages