2026-07-21T16:42:25Zhttps://repisalud.isciii.es/rest/oai/request
oai:repisalud.isciii.es:20.500.12105/234332024-11-28T22:22:33Zcom_20.500.12105_15322com_20.500.12105_2051col_20.500.12105_16967
Repisalud author Coronado, Tomas M author Mir, Arnau author Rossello, Francesc 2024-10-04T13:22:48Z 2024-10-04T13:22:48Z 2022 Coronado 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. 10.1371/journal.pone.0274448 1932-6203 PloS one https://hdl.handle.net/20.500.13003/18873 36395273 L2021275309 2-s2.0-85142178519 https://hdl.handle.net/20.500.12105/23433 926013600015 Divide-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 n eng Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term research article