  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.
