#### Title

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.