First, a lemma: **n < f(n) < 3n**

Proof:

First, the proof that n < f(n):

if f(n) <= n for any n, then f(f(n)) <= f(n), because f is increasing, so

f(f(n)) <= n, but f(f(n)=3n, a contradiction.

Next, the proof that f(n) < 3n

If we let m=f(n), then we just showed that m < f(m), so f(n) < f(f(n))

and f(f(n))=3n, so f(n) < 3n

In particular, the lemma tells us that 1 < f(1) < 3, so f(1)=2.

Thus f(2)=3

f(3)=f(f(2))=6, and f(6)=f(f(3))=9, so f(4) and f(5) are sandwiched between 6 and 9.

Since f is strictly increasing, the values of f(4) and f(5) are "pinned down" to 7 and 8, respectively.

Now we have established the following:

f(1)=2

f(2)=3

f(3)=6

f(4)=7

f(5)=8

f(6)=9

I'm going to stop now, and start over in base 3.

f(1)=2

f(2)=10

f(10)=20

f(11)=21

f(12)=22

f(20)=100

There's a pattern here, which is:

If the first base-3 digit of x is "1" then f(x) is x with the first "1" replaced with "2."

If the first base-3 digit of x is "2" then f(x) is x with the first "2" replaced with a "1", and a "0" appended to the end of it.

This function meets the conditions, because f(x+1)>f(x) and f(f(x)) replaces the first digit of x with a different digit, then replaces the result with the original digit, and a zero is appended to the end of it during one of the steps. In short, f(f(x))=3x.

But is this the only function that meets the conditions?

It's the only function f(x) that meets the conditions when x is a 1-digit number; we've shown that.

Let's assume it's the only function f(x) that meets the conditions when x is an n digit number, and use induction to show it's the only function that meets the conditions when x is an n+1 digit base three number.

If x is an n-digit number of the form 1ddd then f(x)=2ddd, and f(2ddd)=1ddd0, so f(1ddd0)=2ddd0

So f(x) is the only function that meets the conditions when x is an n+1 digit multiple of 3 that begins with "1."

If x is an n+1 digit multiple of 3 beginning with "1", then f(x+3)=f(x)+3. (That's true even if x+3 begins with "2" --

f(12220+3)=f(20000)=100000=22220+3=f(12220)+3)

So in order for f(x+3) > f(x+2) > f(x+1) > f(x) it must be the case that f(x+2)=f(x)+2, and f(x+1)=f(x)+1

So for all n+1 digit numbers beginning with 1, f(1dddd)=2dddd.

Finally, let's look at the n+1 digit numbers beginning with 2.

If 2dddd is an n+1 digit number, then f(1dddd)=2dddd is the only function that meets the requirements, so f(2dddd)=1dddd0, proving that f(x) is the only function that meets the conditions when x is an n+1 digit base three number.

Now, to answer the question at hand…

955 base 10 = 1022101 base 3, and

1684 base 10 = 2022101 base 3, so

f(955)=1684

Lee explained it better:

We have f(f(n))=3n, so f(f(1))=3.

But f is an increasing function, so f(1)=2, f(f(1))=f(2)=3

Let f(3^{k})=p_{k}. So p_{0 }= f(3^{0}) = 2.

f(p_{k}) = f(f(3^{k})) = 3^{k+1}.

p_{k+1 }= f(3^{k+1}) = f(f(p_{k})) = 3p_{k}.

Byinduction, f(3^{k}) = p_{k} = 2*3^{k}.

Also by induction, f(2*3^{k}) = f(p_{k}) = 3^{k+1}.

Notice that the difference f(2*3^{k}) - f(3^{k}) is equal to 2*3^{k }- 3^{k}, which is equal to 3^{k}.

Since f is increasing, and the difference in values of f equals the difference in the arguments to f, it follows that f increases with a slope of 1 on the interval [3^{k}, 2*3^{k}]

So f(3^{k}+r) = f(3^{k})+r = 2*3^{k}+r, where k is a nonnegative integer and 0 £ r £ 3^{k}.

And since 2*3^{k}+r = f(3^{k}+r), it follows that

f(2*3^{k}+r) = f(f(3^{k}+r))

= 3^{k+1}+3r, where k is a nonnegative integer and 0 £

r £ 3^{k}.

As a practical matter, any positive integer can be expressed as either 3^{k}+r or

2*3^{k}+r, where k is a nonnegative integer and 0 £

r £ 3^{k}.

955 happens to be 3^{6}

+ 226, so

f(955) = f(3^{6})+226 = 2*3^{6}+226 = 1684