Coronado, Tomas MMir, ArnauRossello, Francesc2024-10-042024-10-042022Coronado TM, Mir A, Rosselló F. Explicit solution of divide-and-conquer dividing by a half recurrences withpolynomial independent term. PLoS One. 2022;17(11):e0274448.https://hdl.handle.net/20.500.13003/18873https://hdl.handle.net/20.500.12105/23433Divide-and-conquer dividing by a half recurrences, of the form [Formula: see text] 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 xn, 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 nenghttp://creativecommons.org/licenses/by/4.0/RecordsPhylogenyAlgorithmsresearch articleAttribution 4.0 International363952731711e027444810.1371/journal.pone.02744481932-6203PloS oneopen accessFilogeniaAlgoritmosRegistros2-s2.0-85142178519926013600015L2021275309