On 1/31/13, Dan Asimov <dasimov@earthlink.net> wrote:
Parts of what Robert wrote don't use the specified domain and range.
Oh yes! /-: thanks!
But he's right that the constant function f(n) == 2 satisfies all conditions.
OK, let me add that f is *nonconstant*. I hope this makes the asymptotic expression unique. But I don't know that and haven't checked it out
Okay, then it's MCS1733378 : A[0] = 2; A[1] = 3; A[N] = 3 A[N-1] - A[N-2] 2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, 39603, 103682, 271443, 710647, 1860498, 4870847, 12752043, 33385282, 87403803, 228826127, 599074578, ... Way I solved the problem: Make a spreadsheet with N_0 (natural numbers starting at 0) in the left column. Next to N we'll put f(n). Next to 0 put 2, because that's the only value it can have satisfying f(0)^2 = f(0)+2 Next to 1 put "a", which represents an unknown variable. f(1)=a By the f(2n) + 2 = f(n)^2 rule, f(2) must be a^2-2, and f(40 must be (a^2-2)^-2, etc. The first row without an f(n) yet is row 3, so put "b" (another unknown) next to 3. In this way we get a table like this: 0 2 1 a 2 a^2-2 3 b 4 (a^2-2)^2-2 5 c 6 b^2-2 7 8 ((a^2-2)^2-2)^2-2 9 10 c^2-2 Next I choose an a. It can be anything, but I'll just use the smallest valid choice, which is 3. Then we get: 0 2 2 1 a 3 2 a^2-2 7 3 b ? 4 (a^2-2)^2-2 47 5 c ? ... 8 ((a^2-2)^2-2)^2-2 2207 Noting that when we double n, the value of f(n) approximately squares, that implies that b should be close to the geometric mean of 7 and 47. sqrt(7*47 is a little over 18, so I used 18. Now I have 5 terms: 2, 3, 7, 18, 47, ... I looked this up with my recurrence-relation search MCS [1] and found the above solution. You can use a calculator and verify that for the terms shown satisfy A(2*N) = A[N}^2 - 2. - Robert [1] http://mrob.com/pub/math/MCS.html
On 1/30/13, Dan Asimov <dasimov@earthlink.net> 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).
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com