Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term

Abstract

Divide-and-conquer dividing by a half recurrences, of the form x_n = a x_{⌈n/2⌉}+ a x_{⌊n/2⌋}+p(n), n>=2, appear in many areas of applied mathematics, from the analysis of algorithms to the optimization of phylogenetic balance indices. These equations are usually 'solved' by means of a Master Theorem that provides a bound for the growing order of x_n, but not the solution's explicit expression. In this paper we give a finite explicit expression for this solution, in terms of the binary decomposition of n, when the independent term p(n) is a polynomial in ⌈n/2⌉ and ⌊n/2⌋. As an application, we obtain explicit formulas for several sequences of interest in phylogenetics, combinatorics, and computer science, for which no such formulas were known so far: for instance, for the Total Cophenetic index and the rooted Quartet index of the maximally balanced bifurcating phylogenetic trees with n leaves, and the sum of the bitwise AND operator applied to pairs of complementary numbers up to n.