Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term
share
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. The Master Theorems that solve these equations do not provide the solution's explicit expression, only its big-Θ order of growth. In this paper we give an explicit expression (in terms of the binary decomposition of n) for the solution x_n of a recurrence of this form, with given initial condition x_1, when the independent term p(n) is a polynomial in ⌈n/2⌉ and ⌊n/2⌋.
READ FULL TEXT