Find all increasing functions f : N -> N such that f(f(x)) = 3x f(f(f(y))) = 3f(y)
f(3y) = 3f(y)
If we discard the requirement to be an increasing function, one recursively defined solution takes f(3x + 1) = 3x + 2, f(3x + 2) = 3 * (3x + 1), and f(3x) = 3f(x), with f(0) = 0.
Or analogously for any way of splitting the positive integers not divisible by 3 into ordered pairs (a, b). Then define f(3^n a) = 3^n b and f(3^n b) = 3^(n + 1) a. This is the general form of the solutions.
assume f exists
increasing requires that x < f(x) < f(f(x))
f(f(0)) = 3*0 = 0 ≮ 0
therefore f does not exist, qed
For a strictly increasing function change <= to <.
Your argument fails because you drop the antecedent in: x < f(x) => f(x) < f(f(x)). If f(0) = 0, you don’t have 0 < f(0) so can’t require that f(f(0))<f(0).
Note however that it is easy to show that f must be strictly increasing if it is increasing for if x is not y and f(x) = f(y) then 3x = f(f(x)) = f(f(y)) = 3y which cannot be the case.
Edit: derp, it's ℕ, not ℤ⁺.
So there is at least one solution.
The point about sqrt(3) not working for the naturals is a valid point, however.
Headdesk Yes, that's correct; I misparsed "increasing functions f" as "functions f that increase [the value passed through them]" and then got distracted by the discrete vs continuous confusion.