Nested recursions, simultaneous parameters and tree superpositions

zbMATH Open1331.11008arXiv1301.5055MaRDI QIDQ405147FDOQ405147

Mustazee Rahman, Vitaly Kuznetsov, Stephen M. Tanny, Abraham Isgur

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We apply a tree-based methodology to solve new, very broadly defined families of nested recursions of the general form R(n)=sum_{i=1}^k R(n-a_i-sum_{j=1}^p R(n-b_{ij})), where a_i are integers, b_{ij} are natural numbers, and k,p are natural numbers that we use to denote "arity" and "order," respectively, and with some specified initial conditions. The key idea of the tree-based solution method is to associate such recursions with infinite labelled trees in a natural way so that the solution to the recursions solves a counting question relating to the corresponding trees. We characterize certain recursion families within R(n) by introducing "simultaneous parameters" that appear both within the recursion itself and that also specify structural properties of the corresponding tree. First, we extend and unify recently discovered results concerning two families of arity k=2, order p=1 recursions. Next, we investigate the solution of nested recursion families by taking linear combinations of solution sequence frequencies for simpler nested recursions, which correspond to superpositions of the associated trees; this leads us to identify and solve two new recursion families for arity k=2 and general order p. Finally, we extend these results to general arity k>2. We conclude with several related open problems.

Full work available at URL: https://arxiv.org/abs/1301.5055

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

frequency functionmeta-Fibonacci sequencenested recursionsimultaneous parameterslowly growing (or slow) sequencetree superposition

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Other combinatorial number theory (11B75) Recurrences (11B37)

Cites Work

• Trees and meta-Fibonacci sequences
• Solving non-homogeneous nested recursions using trees
• Nested recursions with ceiling function solutions
• Nested recurrence relations with Conolly-like solutions
• A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
• Title not available (Why is that?)
• A combinatorial approach for solving certain nested recursions with non-slow solutions
• On variants of Conway and Conolly's meta-Fibonacci recursions
• Meta-Fibonacci sequences, binary trees and extremal compact codes

Cited In (5)

• Connecting slow solutions to nested recurrences with linear recurrent sequences
• On nested simple recursion
• On the solution space of the Golomb recursion
• Constructing new families of nested recursions with slow solutions
• A combinatorial approach for constructing non-monotonic solutions to the generalized Golomb recursion

This page was built for publication: Nested recursions, simultaneous parameters and tree superpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405147)