Analysis Commons^™

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)$ …