Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems
John C. Kieffer
Abstract
Let k≥2 be a fixed integer. Given a bounded sequence of real numbers (an:n≥k), then for any sequence (fn:n≥1) of real numbers satisfying the divide-and-conquer recurrence fn = (k-mod(n,k))f⌊n/k⌋+mod(n,k)f⌈n/k⌉ + an, n ≥k, there is a unique continuous periodic function f*:ℝ→ℝ with period 1 such that fn = nf*(logkn)+o(n). If (an) is periodic with period k, ak=0, and the initial conditions (fi:1 ≤i ≤k-1) are all zero, we obtain a specific iterated function system S, consisting of k continuous functions from [0,1]×ℝ into itself, such that the attractor of S is {(x,f*(x)): 0 ≤x ≤1}. Using the system S, an accurate plot of f* can be rapidly obtained.
Full Text: PostScript PDF