From Fibonacci numbers to central limit type theorems

详细信息	查看全文 | 推荐本文 |

• 作者：Steven J. Miller^a ; ^{sjm1@williams.edu} ; ^{Steven.Miller.MC.96@aya.yale.edu} ; Yinghui Wang^b ; ^{yw2450@columbia.edu}
• 关键词：Fibonacci numbers ; Zeckendorf始s theorem ; Lekkerkerker始s theorem ; Generating functions ; Partial fraction expansion ; Central limit type theorems ; Far-difference representations
• 刊名：Journal of Combinatorial Theory ; Series A
• 出版年：2012
• 期刊代码：72_00973165
• 类别：mt
• 出版时间：October, 2012
• 卷：119
• 期：7
• 页码：1398-1413
• 文件大小：229 K

摘要

A beautiful theorem of Zeckendorf states that every integer can be written uniquely as a sum of non-consecutive Fibonacci numbers . Lekkerkerker (1951-1952) proved the average number of summands for integers in is , with 蠁 the golden mean. This has been generalized: given non-negative integers with and recursive sequence with , () and (), every positive integer can be written uniquely as under natural constraints on the 始s, the mean and variance of the numbers of summands for integers in are of size n, and as 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 (Gaudet et al., preprint ) 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 始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 .