Computer solutions welcome,
though a proof would be better!

We have f(0) =0 and f(n) = n - f(f(n-1)). Evaluating the initial values trying to find a pattern:

f(0) = 0
f(1) = 1 - f(f(0)) = 1 - f(0) = 1 - 0 = 1
f(2) = 2 - f(f(1)) = 2 - f(1) = 2 - 1 = 1
f(3) = 3 - f(f(2)) = 3 - f(1) = 3 - 1 = 2
f(4) = 4 - f(f(3)) = 4 - f(3) = 4 - 2 = 2
f(5) = 5 - f(f(4)) = 5 - f(2) = 5 - 2 = 3
f(6) = 6 - f(f(5)) = 6 - f(3) = 6 - 3 = 3
f(7) = 7 - f(f(6)) = 7 - f(3) = 7 - 3 = 4
f(8) = 8 - f(f(7)) = 8 - f(4) = 8 - 4 = 4.

It seems to be increasing, with f(n+1) being equal either to f(n) of f(n)+1. And, we are tempted to guess that f(1,000,000,000,000) is equal to 500,000,000,000, admiting that f(n) = 1/2*n (when n is even).

Instead of 1/2 (that you donīt know for sure), letīs make f(n) = k*n, for some k, and try to figure out the right value of k.

Consider the relation f(n)/n.

f(n)/n = (n - f(f(n-1)))/n = 1 - f(f(n-1))/n.

Taking the limit as n goes to infinity, we have:

The lhs is the limit of (f(n)/n), that is k.

The rhs is lim((1 - f(f(n-1))/n) = 1 - lim f(f(n-1))/n = 1 - lim f(k*(n-1))/n = 1 - k*lim f(n-1)/n = 1 - k*k = 1 - k^2.

Thus, we have k = 1 - k^2, which gives the positive root k = (-1 + sqrt(5))/2 = 0.618033988749894...

Examining the values of k*n for integer values of n, we realize that f(n) = [k*(n+1)], being [x] the smallest integer less than or equal to x.

Thus f(1,000,000,000,000) = [618,033,988,749.894...+ 1] = [618,033,988,750.894...] = 618,033,988,750.

(See the correction of the last two lines in my next comment)

Edited on November 15, 2005, 2:17 pm

Edited on November 15, 2005, 3:02 pm

Posted by pcbouhid on 2005-11-15 14:05:50