Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Analysis
An Elementary Approach To Some Analytic Asymptotics, Nicholas Pippenger
An Elementary Approach To Some Analytic Asymptotics, Nicholas Pippenger
All HMC Faculty Publications and Research
Fredman and Knuth have treated certain recurrences, such as $M(0) = 1$ and\[M(n + 1) = \mathop {\min }\limits_{0 \leqslant k \leqslant n} (\alpha M(k) + \beta M(n - k)),\] where $\min (\alpha ,\beta ) > 1$, by means of auxiliary recurrences such as \[h(x) = \left\{ {\begin{array}{*{20}c} {0\qquad {\text{if}}0 \leqslant x < 1,} \\ {1 + h({x / \alpha }) + h({x / \beta }){\text{ if}}1 \leq x < \infty .} \\ \end{array} } \right.\] The asymptotic behavior of $h(x)$ as $x \to \infty $ with $\alpha $ and $\beta $ fixed depends on whether ${{\log \alpha } / {\log \alpha }}$ is rational or irrational.
The solution of Fredman and Knuth used analytic methods in both cases, and used in particular the Wiener–Ikehara Tauberian theorem in the irrational case. The author shows that a more explicit solution to these recurrences can be obtained by entirely elementary methods, based on a geometric interpretation of $h(x)$ …