Solving Non-homogeneous Nested Recursions Using Trees

Details Solving Non-homogeneous Nested Recursions Using Trees Solving Non-homogeneous Nested Recursions Using Trees

2011-05-12

arxiv.org/abs/1105.2351v2

Mathematics

Combinatorics

14 pages

Scientific paper

The solutions to certain nested recursions, such as Conolly's C(n) = C(n-C(n-1))+C(n-1-C(n-2)), with initial conditions C(1)=1, C(2)=2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, which has a natural generalization to a k-term nested recursion of this type, only applies to homogeneous recursions, and only solves each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique can also be used to solve the given non-homogeneous recursion with various sets of initial conditions.

Affiliated with

Also associated with

No associations

Rating

Solving Non-homogeneous Nested Recursions Using Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving Non-homogeneous Nested Recursions Using Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Non-homogeneous Nested Recursions Using Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496463