Given: f is a function with domain and range of the positive integers, and f satisfies these two conditions:

(1) f(n+1) > f(n); that is, f is strictly increasing, and

(2) f(n+f(m)) = f(n)+m+1

Find all possible values of f(2004)

As the domain and range of the function are the positive integers, f(1) must have a positive integral value.  Thus, it could be 1, 2, or some higher positive integer.

Case 1:
Suppose f(1) = 1.  Then in rule (2) let m and n both be 1. That results in a statement that f(2) = 3.  Then let m be 1 and n be 2, so that f(3) = 5.  Then let m be 2 and n be 1, so that f(4) = 4. This means f is not increasing, conflicting with rule (1).

Case 2:
Suppose f(1) = 2. Then, if m = 1 and n = 1, then f(3) = 4. Then let m be 1 and n be 2, so that f(4) = f(2)+2. Since the function is strictly increasing, f(2) and f(4) then have to be 3 and 5 respectively.  This can be continued so that f(x)=x+1 for all x.

Case 3:
Suppose f(1) = a, where a>2.  If m=1 and n=1, then f(a+1) = a + 2.  But if f(1)=a and f(a+1)=a+2, and a>2, then the difference in the independent variables is a, which is greater than 2, but the difference in the dependent variables is only 2.  Thus only one value can fit between the two dependent variables to maintain the strictly increasing nature of the function, but it must serve more than one independent variable. So this case is also impossible.

So case 2 is the only possibility and f(x) = x+1, and in particular, f(2004) = 2005.

Posted by Charlie on 2004-08-28 11:50:11