View Complete Reference

Best, A, Dynes, P, Edelsbrunner, X, McDonald, B, Miller, SJ, Tor, K, Turnage-Butterbaugh, C and Weinstein, M (2017)

Benford Behavior of Generalized Zeckendorf Decompositions

In: Nathanson M. (eds) Combinatorial and Additive Number Theory II. CANT 2015, CANT 2016. Springer Proceedings in Mathematics & Statistics, vol 220. Springer, Cham.

ISSN/ISBN: Not available at this time. DOI: 10.1007/978-3-319-68032-3_3

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 nonadjacent 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{\_}1G{\_}n+{\backslash}cdots +c{\_}LG{\_}{\{}n+1-L{\}}{\$}{\$}with {\$}{\$}c{\_}i{\$}{\$}positive and some other restrictions. Additionally, a set {\$}{\$}S {\backslash}subset {\backslash}mathbb {\{}Z{\}}{\$}{\$}is said to satisfy Benford's law base 10 if the density of the elements in S with leading digit d is {\$}{\$}{\backslash}log {\_}{\{}10{\}}{\{}(1+{\backslash}frac{\{}1{\}}{\{}d{\}}){\}}{\$}{\$}; in other words, smaller leading digits are more likely to occur. We prove that as {\$}{\$}n{\backslash}rightarrow {\backslash}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.

@InProceedings{, author="Best, Andrew and Dynes, Patrick and Edelsbrunner, Xixi and McDonald, Brian and Miller, Steven J. and Tor, Kimsy and Turnage-Butterbaugh, Caroline and Weinstein, Madeleine", editor="Nathanson, Melvyn B.", title="Benford Behavior of Generalized Zeckendorf Decompositions", booktitle="Combinatorial and Additive Number Theory II", year="2017", publisher="Springer International Publishing", address="Cham", pages="25--37", isbn="978-3-319-68032-3", doi="10.1007/978-3-319-68032-3_3", }

Reference Type: Conference Paper

Subject Area(s): Number Theory