Let f be a function from Z+ to Z+ where Z+ is the set of positive integers, such that 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 values of f(2003)

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.