Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term
Tomás M Coronado,
Arnau Mir and
Francesc Rosselló
PLOS ONE, 2022, vol. 17, issue 11, 1-37
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 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.
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0274448 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 74448&type=printable (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0274448
DOI: 10.1371/journal.pone.0274448
Access Statistics for this article
More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().