Let be a function such that and for all . Evaluate .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Note that by extension of f ( n + 1 ) > f ( n ) we have f ( m ) > f ( n ) whenever m > n .
We will prove via induction on all non-negative integers n a claim P n that:
First, we prove that f ( 1 ) = 2 .
If f ( 1 ) = 1 , we have f ( f ( 1 ) ) = 1 = 3 , a contradiction, hence f ( 1 ) > 1 and with the condition f ( n + 1 ) > f ( n ) , we have f ( n ) > n for all positive integers n .
If f ( 1 ) ≥ 3 , we'd have f ( f ( 1 ) ) ≥ f ( 3 ) > 3 , also a contradiction. Hence we must have f ( 1 ) = 3 . Also, we have f ( 2 ) = f ( f ( 1 ) ) = 3 and f ( 3 ) = f ( f ( 2 ) ) = 6 .
We note that we have our claim P n be true for n = 0 , given our values of f ( 1 ) , f ( 2 ) , f ( 3 ) . Now assume for some non-negative integer k , we have P k be true, i.e. that:
We then consider the claim P k + 1 :
For 3 k + 1 ≤ x ≤ 2 ⋅ 3 k + 1 , consider the x where x = 3 y for some integer 3 k ≤ y ≤ 2 ⋅ 3 k . We then have x = f ( f ( y ) ) = f ( y + 3 k ) , and consequently f ( x ) = f ( f ( y + 3 k ) ) ) = 3 ( y + 3 k ) = 3 y + 3 k + 1 = x + 3 k + 1 .
For 3 k + 1 ≤ x ≤ 2 ⋅ 3 k + 1 , there also exist x , x + 1 where 3 y < x < x + 1 < 3 ( y + 1 ) for some ( 3 k ≤ y ≤ 2 ⋅ 3 k − 1 . We can infer that x = 3 y + 1 , x + 1 = 3 y + 2 . Then using our results that f ( 3 y ) = 3 y + 3 k + 1 , f ( 3 y + 3 ) = 3 y + 3 + 3 k + 1 from just now, we have:
3 y + 3 k + 1 = f ( 3 y ) < f ( x ) < f ( x + 1 ) < f ( 3 y + 3 ) = 3 y + 3 + 3 k + 1
We thus have f ( x ) = 3 y + 1 + 3 k + 1 = x + 3 k + 1 , f ( x + 1 ) = 3 y + 2 + 3 k + 1 = x + 1 + 3 k + 1 , hence we have it that for all 3 k + 1 ≤ x ≤ 2 ⋅ 3 k + 1 , we have f ( x ) = x + 3 k + 1
For 2 ⋅ 3 k + 1 ≤ x ≤ 3 k + 2 , we note that 3 k + 1 ≤ x − 3 k + 1 ≤ 2 ⋅ 3 k + 1 and from our previous result we have f ( x − 3 k + 1 ) = x − 3 k + 1 + 3 k + 1 = x . Consequently, we have f ( x ) = f ( f ( x − 3 k + 1 ) ) = 3 x − 3 k + 2 .
Thus we have proven that with P 0 being true and P k being true ⇒ P k + 1 being true, we have proven our claim that P n is true for all non-negative integers n.
Given that 2 ⋅ 3 6 ≤ 2 0 0 1 ≤ 3 7 , we apply our formula to get f ( 2 0 0 1 ) = 3 ⋅ 2 0 0 1 − 3 7 = 3 8 1 6