Solve $f(f(n))=n!$

Question

What am I doing wrong here: ( n!=factorial )
Find $f(n)$ such that $f(f(n))=n!$

$$f(f(f(n)))=f(n)!=f(n!).$$

So $f(n)=n!$ is a solution, but it does not satisfy the original equation except for $n=1$, why?

How to solve $f(f(n))=n!$?

Answer 1

What you have to do is partition the natural numbers into chains of iterates of the factorial function:

$0, 1, 1, 1, \dots$

$2,2,\dots$.

$3,3!,3!!,3!!!,\dots$

$4, 4!, 4!!, \dots $

You go on by starting the next chain with the smallest natural number that has not yet been used.

Except for the first two chains, no chain will have repeated values and since the function $n!$ is injective for positive $n$, the chains will be disjoint.

Now, to find $f$, setting $f(0)=f(1)=1$ and $f(2)=2$ will give the desired relation for these values.

For all the other values, you pair up the chains, and for a pair of chains

$a_1,a_2,\dots$

$b_1,b_2,\dots$

you set $f(a_k)=b_k$ and $f(b_k)=a_{k+1}$.

This ensures that $f\circ f$ just moves one step along each chain as it should to satisfy your equation.

As you can see, you have a lot of choice in pairing up the chains.

Answer 2

You just found out that if $f(f(n)) = n!$, then also $f(n)! = f(n!)$. That does not means that any function that satisfies the latter equation is a valid $f$.

Answer 3

The hypothesis is $f(f(n))=n!$. This implies that $f(n)!=f(n!)$ like you say, but unfortunately the converse is not true; you can't reverse the direction and say that a function satisfying the latter equation also satisfies $f(f(n))=n!$. For a similar situation, suppose we have $x=1$ and square it to obtain $x^2=1$; now $x=-1$ is a solution to the latter equation but clearly $-1\ne+1$ so we've "lost information" by squaring.