Asymptotic analysis of a class of functional equations and applications
Journal de Théorie des Nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 365-381.

Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for z by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of N people is computed, where each person advances one step or dies with equal probabilities, and an additional “killer” can kill at any level up to d survivors, according to his probability distribution.

@article{JTNB_1993__5_2_365_0,
     author = {Grabner, Peter J. and Prodinger, H. and Tichy, R. F.},
     title = {Asymptotic analysis of a class of functional equations and applications},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {365--381},
     publisher = {Universit\'e Bordeaux I},
     volume = {5},
     number = {2},
     year = {1993},
     zbl = {0797.39008},
     mrnumber = {1265911},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_1993__5_2_365_0/}
}
Grabner, P. J.; Prodinger, H.; Tichy, R. F. Asymptotic analysis of a class of functional equations and applications. Journal de Théorie des Nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 365-381. http://www.numdam.org/item/JTNB_1993__5_2_365_0/

[1] T.M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984. | MR 434929 | Zbl 0335.10001

[2] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoret. Comput. Sci. (to appear). | MR 1256203 | Zbl 0788.44004

[3] P. Flajolet and L.B. Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305-320. | MR 1164843 | Zbl 0758.60015

[4] P. Flajolet, M. Régnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer, New York, 1985. | MR 815343 | Zbl 0582.68015

[5] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216-240. | MR 1039294 | Zbl 0712.05004

[6] P. Flajolet and J. Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A "Algorithms and Complexity" North-Holland, 1990, 431-524. | MR 1127175 | Zbl 0900.68251

[7] D.E. Knuth, The Art of Computer Science Vol. 3, Addison Wesley, Reading, MA, 1973.

[8] H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992. | MR 1140708 | Zbl 0762.68033

[9] J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad. 59 (1983), 441-444. | MR 732606 | Zbl 0541.10040

[10] H. Prodinger, How to, Advance on a Staircase by Coin Flippings,, Proceedings "Fibonacci Numbers and Applications 5" (1992) (to appear). | Zbl 0807.68056

[11] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927. | JFM 53.0180.04