If f(f(x))=x²+x-1, what is f(x)

Answer 1

A very interesting and difficult question for how simple it is to state!

If x is allowed to be a complex number and f is allowed to be complex-valued, the answer is that there are no solutions to this functional equation, see this paper from Rice, Schweizer, and Sklar (1980): http://yaroslavvb.com/papers/rice-when.pdf. The techniques involved in the proof go a bit beyond my expertise, but the paper appears to be well-written.

If x is restricted to be a real-number and f is restricted to be a real-valued function, then there are several answers to this functional equation, see the following discussion on Math StackExchange: https://math.stackexchange.com/questions/1158619/do-there-exist-functions-f-such-that-ffx-x2-x1-for-every-x. In particular, there's a delightful proof that shows that there is at most one continuously differentiable real-valued function f that satisfies the functional equation. Constructing this function is not an easy task, though.

Answer 2

This isn't a full answer, but it's a clue

If f(f(x)) = x^2

then f(x) = x^(sqr2) = about x^1.414

f(f(x))= f(x^(sqr2)) = (x^sqr2)^sqr2 = x^(sqr2(sqr2)) = x^2

using that ...