Accession Number : AD0748606

Title :   Growth Properties of a Class of Recursively Defined Functions,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Fredman,Michael L.

Report Date : JUN 1972

Pagination or Media Count : 86

Abstract : Let alpha and beta be positive real constants, and let g(n) be a real-valued function over the nonnegative integers. Consider the function M(n) defined as follows: M(0) = g(0) and M(n+1) = g(n+1) + min (alpha M(k) + beta M(n-k)) 0< or = K < or = 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, some of which are often encountered in analytic number theory. Special cases of these recurrences lead to a surprising number of interesting problems involving both discrete and continuous mathematics. (Author)

Descriptors :   (*RECURSIVE FUNCTIONS, THEOREMS), ANALYTIC FUNCTIONS, NUMBER THEORY, POLYNOMIALS, DYNAMIC PROGRAMMING, ALGORITHMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE