Sums of ceiling functions solve nested recursions

Abstract

It is known that, for given integers and j>0, the nested recursion has a closed-form solution for which a combinatorial interpretation exists in terms of an infinite, labelled tree. For s = 0, we show that this solution sequence has a closed form as the sum of ceiling functions

Furthermore, given appropriate initial conditions, we derive necessary and sufficient conditions on the parameters and so that solves the nested recursion .

Keywords:

• nested recursion
• ceiling function
• formal satisfaction
• equivalence class

Keywords:

• 11B37
• 11-04

Notes

1. It is also shown in Ref. [4] that for every , the ceiling function solves an infinite family of order p nested recursions. In this paper we restrict our attention to the recursion (1), which has order 1.