tailieunhanh - Báo cáo toán học: "Trees and Meta-Fibonacci Sequences"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Trees and Meta-Fibonacci Sequences. | Trees and Meta-Fibonacci Sequences Abraham Isgur David Reiss and Stephen Tanny Department of Mathematics University of Toronto Ontario Canada tanny@ Submitted Apr 3 2009 Accepted Oct 21 2009 Published Oct 31 2009 Mathematics Subject Classification 05A15 11B37 11B39 05C05 Abstract For k 1 and nonnegative integer parameters ap bp p we analyze the solutions to the meta-Fibonacci recursion C n 52p i C n ap C n bp where the parameters ap bp p satisfy a specific constraint. For k 2 we present compelling empirical evidence that solutions exist only for two particular families of parameters special cases of the recursions so defined include the Conolly recursion and all of its generalizations that have been studied to date. We show that the solutions for all the recursions defined by the parameters in these families have a natural combinatorial interpretation they count the number of labels on the leaves of certain infinite labeled trees where the number of labels on each node in the tree is determined by the parameters. This combinatorial interpretation enables us to determine various new results concerning these sequences including a closed form and to derive asymptotic estimates. Our results broadly generalize and unify recent findings of this type relating to certain of these meta-Fibonacci sequences. At the same time they indicate the potential for developing an analogous counting interpretation for many other meta-Fibonacci recursions specified by the same recursion for C n with other sets of parameters. 1 Introduction In this paper all values are integers. For k 1 and nonnegative parameters ap bp p consider the general meta-Fibonacci also called self-referencing or nested homogeneous recursion k C n C n ap C n bp p i Many well-known meta-Fibonacci recursions with appropriate initial conditions are special cases of which we often write as a1 b1 a2 b2 ak bk . For example the THE .