An Elementary Approach to some Analytic Asymptotics
Document Type
Conference Proceeding
Department
Mathematics (HMC)
Publication Date
7-1992
Abstract
Fredman and Knuth have treated certain recurrences, such as M(0) = 1 and
M(n+1) = min 0≤k≤n (αM(k) + βM(n-k)),
where min(α,β) > 1. Their treatment depends on certain auxiliary recurrecnes, such as
h(x) = 0, if 0 ≤ x < 1; h(x) = 1 + h(x/α) + h(x/β), if 1 ≤ x < ∞.
The asymptotic behavior of h(x) as x→∞ with α and β fixed depends on whether log α/ log β 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. We show that a more explicit solutions 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, we need in the irrational case only the Kronecker-Weyl theorem (which can itself be proved by elementary methods), to the effect that if ϑ is irrational, the fractional parts of the sequence ϑ, 2ϑ, 3ϑ, ... are uniformly distributed in the unit interval.
Rights Information
© 1992 Springer
DOI
10.1007/3-540-55706-7_5
Recommended Citation
Pippenger, Nicholas. "An Elementary Approach to some Analytic Asymptotics."Proc. Scand. Workshop on Algorithm Theory 3 (1992), 53-61.
