On Golomb's self describing sequence. II (Q1816489): Difference between revisions

[Part I, cf. J. Number Theory 53, 13-24 (1995; Zbl 0839.11005).] Let \(\{F (n) \}^\infty_{n=1}= \{1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, \dots\}\) be Golomb's self-describing sequence, defined by the condition (i) \(F(1)= 1\); (ii) \(F(n)\) nondecreasing; (iii) \(F(n)\) is the number of integers \(k\) for which \(F(k) =n\). It is known that \(F(n) \sim \varphi^{2- \varphi} n^{\varphi -1}\) as \(n\to \infty\), where \(\varphi= (\sqrt {5}+ 1)/2\) is the golden number, and at least one complete proof of this exists [\textit{N. J. Fine}, Am. Math. Mon. 74, 740-743 (1967)]. There is also a very nice heuristical argument in favor of this, due to \textit{D. Marcus} (loc. cit. p. 740). Briefly, it goes as follows. It seems plausible (1) that there is a good approximation \(f\) of \(F\) which is differentiable and satisfies the approximate functional-differential equation \(f'(t)= (1+ o(1))/ f(f (t))\); and (2) that such an \(f\) satisfies \((*)\) \(f(t) \sim \varphi^{2- \varphi} t^{\varphi-1}\), the latter expression being the unique continuous solution of the functional differential equation \(g(t)= g'(t)/ g(g(t))\) \((t>0)\) with initial condition \(g(0)=0\). The present paper provides complete proofs of (1) and (2), and proposes \((*)\) as an exercise.