Mentor: Dr. Steven Miller (Williams College)

Title: Extending Zeckendorf's Theorem to a Non-constant Recurrence

Abstract: Zeckendorf's Theorem states that every positive integer can be uniquely represented as a sum of non-adjacent Fibonacci numbers, indexed from 1,2,3,5,…. This has been generalized by many authors, in particular to constant coefficient fixed depth linear recurrences with positive (or in some cases non-negative) coefficients. In this work we extend this result to a recurrence with non-constant coefficients, an+1=nan+an−1. The decomposition law becomes every m has a unique decomposition as ∑siai with si≤i, where if si=i then si−1=0. Similar to Zeckendorf's original proof, we use the greedy algorithm. We show that almost all the gaps between summands, as n approaches infinity, are of length zero, and give a heuristic that the distribution of the number of summands tends to a Gaussian.