Let and , where . Then a theorem of Carlitz et al. states that each function f, composed of several a's and b's, can be expressed in the form c₁a + c₂b - c₃, where c₁ and c₂ are consecutive Fibonacci numbers determined by the numbers of a's and of b's composing f and c₃ is a nonnegative constant. We provide generalizations of this theorem to two infinite families of complementary pairs of Beatty sequences. The particular case involving `Narayana' numbers is examined in depth. The details reveal that , with n nested pairs of , is a 7th-order linear recurrence, where is the dominant zero of x³ - x² - 1.