2014/12/21 by Best, Andrew, Dynes, Patrick, Edelsbrunner, Xixi +5
#11B05 #11B39 #11K06 #60F05(primary) #62E20(secondary) #65Q30 #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1412.6839
We prove connections between Zeckendorf decompositions and Benford's law. Recall that if we define the Fibonacci numbers by F1 = 1, F2 = 2 and Fn+1 = Fn + Fn-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 Gn+1=c1Gn+⋯+cLGn+1-L with ci positive and some other restrictions. Additionally, a set S ⊂ ℤ is said to satisfy Benford's law base 10 if the density of the elements in S with leading digit d is log10(1+(1)/(d)); in other words, smaller leading digits are more likely to occur. We prove that as n→∞ for a randomly selected integer m in [0, Gn+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.