On 1/30/2013 10:26 PM, Dan Asimov wrote:
While studying something apparently unrelated, I came upon a function
f: N_0 -> N_0
(where N_0 denotes {0,1,2,3,...})
with this curious property:
f(2n) + 2 = f(n)^2.
Puzzle: Find a closed-form asymptotic expression for f(n).
Since f(2n) is determined by f(n), all the values are determined by the values for n odd (and for n = 0, where we must have f(0) = 2). There is no restriction on the values of f(n) for n odd except that f(n), f(2n), f(4n), etc. are all >= 0; this is satisfied whenever f(n) >= 2. So we have countably many independent choices to make; there are thus uncountably many functions f satisfying the given conditions. In a follow-up message, Dan ruled out the constant function 2, but there are still lots of functions which are "mostly" 2; for example, the function which is 2 for all n not of the form 239*2^n, and with f(239) = 4, f(478) = 14, f(956) = 194, etc. Coming up with the intended answer seems to require reading Dan's mind. Fortunately, I have a seldom-used Transilience Thought Unifier Model-11 here, so I'll give it a try. Hmm. There seems to be some interference, but I think I see the following sequence (starting with f(0)): 2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, ... This is the subsequence of the Lucas sequence consisting of the terms with even index. Since L(n) = phi^n + (-1/phi)^n, f(n) = L(2n) is asymptotic to phi^{2n}, where phi is the golden ratio. -- Fred W. Helenius fredh@ix.netcom.com