GENERALIZING ZECKENDORF’S THEOREM TO f-DECOMPOSITIONS

ABSTRACT. A beautiful theorem of Zeckendorf states that every positive integer can be uniquely decomposed as a sum of non-consecutive Fibonacci numbers {Fn}, where F1 = 1, F2 = 2 and Fn+1 = Fn + Fn−1. For general recurrences {Gn} with non-negative coefficients, there is a notion of a legal decomposition which again leads to a unique representation, and the number of sum-mands in the representations of uniformly randomly chosen m ∈ [Gn, Gn+1) converges to a normal distribution as n→∞. We consider the converse question: given a notion of legal decomposition, is it possible to con-struct a sequence {an} such that every positive integer can be decomposed as a sum of terms from the sequence? We encode a notion of legal decomposition as a function f: N0 → N0 and say that if an is in an “f-decomposition”, then the decomposition cannot contain the f(n) terms immediately before an in the sequence; special choices of f yield many well known decompositions (including base-b, Zeckendorf and factorial). We prove that for any f: N0 → N0, there exists a sequence {an}∞n=0 such that every positive integer has a unique f-decomposition using {an}. Further, if f is periodic, then the unique increasing sequence {an} that corresponds to f satisfies a linear recurrence relation. Previous research only handled recurrence relations with no negative coefficients. We fin