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. | 