NESTED RECURRENCE RELATIONS WITH CONOLLY-LIKE SOLUTIONS

摘要

A nondecreasing sequence of positive integers is (α, β)-Conolly, or Conolly-like for short, if for every positive integer m the number of times that m occurs in the sequence is α + β_(rm), where r_m is 1 plus the 2-adic valuation of m. A recurrence relation is (α,β)-Conolly if it has an (α, β)-Conolly solution sequence. We discover that Conolly-like sequences often appear as solutions to nested (or meta-Fibonacci) recurrence relations of the form A(n) = ∑_i~k=A(n-s_i-∑_(j=1)~)(Pi) A(n-a_(ij))) with appropriate initial conditions. For any fixed integers k and P_1,P_2, ... ,P_k we prove that there are only finitely many pairs (α,β) for which A(n) can be (α, β)-Conolly. For the case where α = 0 and β = 1, we provide a bijective proof using labeled infinite trees to show that, in addition to the original Conolly recurrence, the recurrence H(n) = H(n - H(n - 2)) + H(n - 3 - H(n - 5)) also has the Conolly sequence as a solution. When k = 2 and P_1 = P_2, we construct an example of an (α,β)-Conolly recursion for every possible (α, β) pair, thereby providing the first examples of nested recursions with p_i > 1 whose solutions are completely understood. Finally, in the case where k = 2 and p_1 = p_2, we provide an if and only if condition for a given nested recurrence A(n) to be (α, 0)-Conolly by proving a very general ceiling function identity.