A combinatorial approach for solving certain nested recursions with non-slow solutions

2012/02/01 by Abraham Isgur, Vitaly Kuznetsov, Isgur, Abraham +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1202.0276

To appear in "Journal of Difference Equations and Applications"

arxiv created 2012/02/01 · openalex publication_date 2012/02/01 · arxiv updated 2012/02/03 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We define the generalized Golomb triangular recursion by g_j,s,lambda(n) = g_j,s,lambda(n - s - g_j,s,lambda(n-j)) + λj. For particular choices of the initial conditions, we show that the solution of the recursion is a non-slow monotone sequence for which we can provide a combinatorial interpretation in terms of a weighted count of the leaves of a certain labeled infinite tree. We discover that more than one such tree interpretation is possible, leading to different choices of the initial conditions and alternative solutions that are closely related. In the case lambda=1 the initial conditions for these alternative tree interpretations coincide and we derive explicit closed forms for the solution sequence and its frequency function.

Related

• Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences
• Sums of Ceiling Functions Solve Nested Recursions
• Averaged Extensions of Golomb's Triangular Recursion: Critical Invariance and Supercritical Constraints
• An elementary approach to solve recursions relative to the enumeration of S-Motzkin paths
• Generalized Monotone Triangles: an extended Combinatorial Reciprocity Theorem