Recurrence Relations Based on Minimization.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The paper investigates solutions of the general recurrence M0 g0, Mn1 gn1 minsub 0 or k or n alpha Mk beta Mn-k for various choices of alpha, beta, and gn. In a large number of cases it is possible to prove that Mn is a convex function whose values can be computed much more efficiently than would be suggested by the defining recurrence. The asymptotic behavior of Mn can be deduced using combinatorial methods in conjunction with analytic techniques. In some cases there are strong connections between Mn and the function Hx defined by Hx 1 for x 1, Hx Hx-1alpha Hx-1beta for x or 1. Special cases of these recurrences lead to a surprising number of interesting problems involving both discrete and continuous mathematics. Author
- Theoretical Mathematics
- Operations Research