Accession Number : AD0739335
Title : Recurrence Relations Based on Minimization.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Fredman,Michael L. ; Knuth,Donald E.
Report Date : DEC 1971
Pagination or Media Count : 40
Abstract : The paper investigates solutions of the general recurrence M(0) = g(0), M(n+1) = g(n+1) + min(sub 0 < or = k < or = n) (alpha M(k) = beta M(n-k)) for various choices of alpha, beta, and g(n). In a large number of cases it is possible to prove that M(n) is a convex function whose values can be computed much more efficiently than would be suggested by the defining recurrence. The asymptotic behavior of M(n) can be deduced using combinatorial methods in conjunction with analytic techniques. In some cases there are strong connections between M(n) and the function H(x) defined by H(x) = 1 for x < 1, H(x) = H((x-1)/alpha + H((x-1)/beta) for x > or = 1. Special cases of these recurrences lead to a surprising number of interesting problems involving both discrete and continuous mathematics. (Author)
Descriptors : (*DYNAMIC PROGRAMMING, *CONVEX SETS), FUNCTIONS(MATHEMATICS), ASYMPTOTIC SERIES, COMBINATORIAL ANALYSIS, INTEGRALS, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE