Document Type

Article

Department

Mathematics (HMC)

Publication Date

1993

Abstract

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)$ as a sum of binomial coefficients over a triangular subregion of Pascal’s triangle. Apart from Stirling's formula, in the irrational case only the Kronecker–Weyl theorem (which can itself be proved by elementary methods) is needed, to the effect that if is irrational, the fractional parts of the sequence $\vartheta ,2\vartheta ,3\vartheta , \cdots $, are uniformly distributed in the unit interval.

Rights Information

© 1993 Society for Industrial and Applied Mathematics

Download

Included in

Analysis Commons

Share

COinS