Treffer: On representations of positive integers in the Fibonacci base

We exhibit and study various regularity properties of the sequence (R(n))n≥1 which counts the number of different representations of the positive integer n in the Fibonacci numeration system. The regularity properties in question are observed by representing the sequence as a two-dimensional array consisting of an infinite number of rows L1, L2, L3,... where each Lk contains fk-1 (the k - 1st Fibonacci number) entries of the sequence (R(n)). We give a purely combinatorial recursive algorithm for generating each row Lk from previous rows Lj with j < k. We then show that for each positive integer m, and for all k ≥ 2m, the number of occurrences of m in Lk is a constant rk(m) depending only on m. The function rk(m) has many interesting number theoretic properties and is intimately connected to the Euler Φ-function.