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

作者：Isgur Abraham; Kuznetsov Vitaly; Tanny Stephen M^*

来源：Journal of Difference Equations and Applications, 2013, 19(4): 605-614.

DOI：10.1080/10236198.2012.662967

• nested recursion
• slowly growing sequence
• non-homogeneous Conolly recursion
• Golomb triangular recursion

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)) + lambda(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 labelled 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.

• 出版日期2013-4-1