On variants of Conway and Conolly's meta-Fibonacci recursions (Q540094)

Summary: We study the recursions \(A(n) = A(n-a-A^k(n-b)) + A(A^k(n-b))\) where \(a \geq 0\), \(b \geq 1\) are integers and the superscript \(k\) denotes a \(k\)-fold composition, and also the recursion \(C(n) = C(n-s-C(n-1)) + C(n-s-2-C(n-3))\) where \(s \geq 0\) is an interger. We prove that under suitable initial conditions the sequences \(A(n)\) and \(C(n)\) will be defined for all positive integers, and be monotonic with their forward difference sequences consisting only of 0 and 1. We also show that the sequence generated by the recursion for \(A(n)\) with parameters \((k,a,b) = (k,0,1)\), and initial conditions \(A(1) = A(2) = 1\), satisfies \(A(E_n) = E_{n-1}\) where \(E_n\) is a generalized Fibonacci recursion defined by \(E_n = E_{n-1} + E_{n-k}\) with \(E_n = 1\) for \(1 \leq n \leq k\).