Linear divide-and-conquer recurrences translate into linear Mahler equations for the generating functions of the sequences. For example the recurrence for the Karatsuba algorithm complexity \[ u_n = u_{\lfloor n/2 \rfloor} + u_{\lceil n/2 \rceil} + n - 1 \] translates into \[ u(x) = \frac{(1+x)(2+x)}{x} u(x^2) - x + \frac{4 x^2}{(1-x)^2}.\]

The search for solutions of these functional equations in some classes of functions is motivated by two reasons. First there is a general trend to solve functional equations, that has begun with the work of Liouville (1833) about differential equations and was continued by Abramov (1989) for recurrences. Particularly the search for rational solutions is a building block for other algorithms (like summation algorithms). Next Mahler equations are related to transcendence issues. This standpoint comes from Mahler's work (1929, 1930) about this topic. Recently several works (Adamcwezski and Faverjon, 2015; Dreyfus, Hardouin, and Roques, 2015, among others) provide criteria to recognize if an object is transcendental and these criteria are based on the existence of solutions of a given type for some Mahler equations.

This leads to the writing of an article Computing solutions of linear Mahler equations, 2016, you can find in the page devoted to my publications.