Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms

We study a recurrence equation of type \[ l_n (2n + s - 2) = 2^n a_n + ∑k = 1n - 1 {matrix} n \\ k {matrix} l_k , n N \] where aₙ is any sequence and $s,N$ are integers. This type of recurrence arises in many applications in computer sciences and telecommunications, e.g., in the analysis of unsuccessful search in a family of Patricia trees, in the average complexity of an algorithm generating exponentially distributed variates, in trie statistics, in the performance evaluation of conflict resolution algorithms in a broadcast communication environment, etc. We present a closed-form solution of the recurrence and then we establish an asymptotic approximation for it. In addition, we offer an approximation of a generating function, $l(z)$, of lₙ for small values of z.