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.