If f(0)=0 and for n>0, f(n)=n-f(f(n-1)),
what is f(1,000,000,000,000)?
Computer solutions welcome,
though a proof would be better!
|
|
Submitted by e.g.
|
|
Rating: 3.1667 (6 votes)
|
|
|
Solution:
|
(Hide)
|
|
Clearly f(n) is always less than n, and checking the first few values by hand it appears to be increasing, with f(n+1) equaling either f(n) or f(n)+1. A reasonable guess is that f(n) is approximately c*n, for some constant c. To find what c is if this is the case, consider f(n)/n = 1 - f(f(n-1)))/n. In the limit as n goes to infinity, the left side becomes c, and the right side becomes 1 - c². Since one must equal the other c=1-c², and rejecting the negative root we have that c is ½(-1+√5). Examining the values of c*n rapidly leads to the conclusion that f(n)= [c*(n+1)], where [x] is the smallest integer less than or equal to x.
To prove this, note that if x>0 is not an integer, then [-x] = -[x] - 1. Now n - [c*[c*n] + c] = n + [-c*[c*n] - c] + 1 = n + 1 + [ -c^2*n - c*e - c ], where e = c*n - [c*n]. Since c^2 = 1-c, this equals n + 1 + [-n - c*n - c*e - c] = 1 + [c*n - c*e - c] = [c*n + c] + [f - c*e - 2c + 1], where f = c*n + c - [c*n + c]. Now if e+c<1, f=e+c; if e+c ≥ 1, f=e+c-1. It follows easily from this that [f - c*e - 2c + 1] is always 0. Since f(0) = 1 = [c*0 + c], the truth of our hypothesis follows, and it also follows that f(1000000000000) = 618033988750. |
