First a hint...

 

Do these three things:

 

 

1. Prove f(n) ³ n for all n 

2. Suppose f(n)=n for some n and derive a contradiction. 

3. Suppose there is an n with f(n)=n+k some k ³ 2 and find a contradiction.

 

 

STOP READING HERE IF YOU WANT TO TRY THIS YOURSELF!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Proof that f(n) ³ n for all n

 

 

f(1) ³ 1 because f goes from Z+ to Z+

if f(k) ³ k then f(k+1) > f(k) ³
k, so f(k+1) > k, so f(k+1) ³ k+1

 

 

2. Proof that f(n)>n

 

 

Suppose an n exists such that f(n)=n

f(n-1) is strictly smaller than n, and f(n-1) ³
n-1 (from th. 1) so f(n-1)=n-1

So all numbers k < n have the property that f(k)=k.

In particular f(1)=1, so

f(2) = f(1+f(1)) = f(1)+1+1 = 3, and

f(3) = f(2+f(1)) = f(2)+1+1 = 5, but

f(4) = f(1+f(2)) = f(1)+2+1 = 4, so f is not strictly increasing,contradicting the assumption that f(n)=n, and thus proving that f(n)>n

 

 

3. Proof that f(n) £ n+1

 

 

Suppose f(n)=n+k, where k ³ 2 and n is a positive integer

Since f is strictly increasing, it follows that

 

 

(stmt 1) for all p ³ n, f(p) ³
p+k, and

(stmt 2) for all q £ n, f(q) £
q+k

 

 

f(1+n+k)=f(1+f(n)) = f(1)+n+1 ³ (1+n+k)+k by
stmt 1, above

so f(1) ³ 2k, contradicting stmt 2

 

 

Together, 1, 2, and 3 show that f(n)=n+1

So f(2003)=2004

 

 

Sasha explained it more simply:

 

 

Let f(1)=x, where x is a particular positive integer.

 

 

f(1+f(1)) = f(1+x) = f(1)+2 = x+2

 

 

It's clear that x is not equal to 1 [convince yourself by calculating
f(2)=f(1+f(1)), f(3)=f(2+f(1)), and f(4)=f(1+f(2))]

 

 

Since f(1)=x and f(x+1)=x+2, and since x is between 1 and x+1, it
follows that f(x)=x+1.

 

 

Since x is the smallest value that f can take on, x+1 is the second-smallest value that f can take on. Together with the fact that f(x)=x+1, we conclude that x=2.  In other words, f(1)=2. We also know that f(2)=3.

 

 

If k is any positive integer, then f(k+2) = f(k+f(1)) = f(k)+2

 

 

This, together with the facts that f(1)=2 and f(2)=3 (which we also learned, above), it follows by induction that f(k)=k+1 for all k.

 

 

Lee has a clever approach:

 

 

From the first rule of the problem, we deduce the following fact:

 

 

If f(a) - f(b) = 1 then a-b=1

 

Do you need a proof?  Here it is...

 

Suppose a-b > 1.  Then there is a number, c, with b < c < a, and f(b) < f(c) < f(a), but this is impossible because there is no integer between f(b) and f(a).

 

Suppose a-b = 0.  Then a=b so f(a)=f(b), another contradiction.

 

Suppose a-b < 0.  Then a < b, but f(a) > f(b), contradicting rule 1.

 

Having reached contradictions for all situations other than a-b=1, it follows that a-b=1.

 

 

From the second rule of the problem, we know the following:

 

 

(1)   f(n+f(n)) = f(n)+n+1

 

 

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

 

 

Combining 1 and 2, we see that f(n+f(n)) = f(n+f(n-1)) + 1, so

 

 

n+f(n) - (n+f(n-1)) = 1, so

 

 

(3)   f(n) - f(n-1) = 1

 

 

Now if we only knew what f(1) was, then we would know the value of any f(n). Lee has a clever way of getting this, too.

 

 

Let p = 1+f(1).  Then from (1), we get f(p)=p+1.

 

 

From (3), we get f(p-1)=p.

 

From (3) again, we know this: If f(p-k)=p-k+1, then
f(p-(k+1))=p-(k+1)+1, and by induction we get f(1)=2.