NESTED RECURRENCE RELATIONS WITH CONOLLY-LIKE SOLUTIONS

作者：Erickson Alejandro^*; Isgur Abraham; Jackson Bradley W; Ruskey Frank; Tanny Stephen M

来源：SIAM Journal on Discrete Mathematics, 2012, 26(1): 206-238.

DOI：10.1137/100795425

• self-referencing recursion
• nested recursion
• slowly growing sequence
• Conolly-like
• ruler function
• meta-Fibonacci
• bijective proof
• infinite trees
• ceiling function identity

A nondecreasing sequence of positive integers is (alpha, beta)-Conolly, or Conolly-like for short, if for every positive integer m the number of times that m occurs in the sequence is alpha + beta r(m), where r(m) is 1 plus the 2-adic valuation of m. A recurrence relation is (alpha, beta)-Conolly if it has an (alpha, beta)-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) = Sigma(k)(i=1) A(n-s(i)-Sigma(pi)(j=1) 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 (alpha, beta) for which A(n) can be (alpha, beta)-Conolly. For the case where alpha = 0 and beta = 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 (alpha, beta)-Conolly recursion for every possible (alpha, beta) pair, thereby providing the first examples of nested recursions with p(i) %26gt; 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 (alpha, 0)-Conolly by proving a very general ceiling function identity.

• 出版日期2012