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

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!$?

-
I removed functional analysis tag. Functional analysis deals with completely different types of problems –  Beni Bogosel Nov 22 '11 at 18:38
I don't think that $f(n) = 1$ solves your equation as $1 = f(f(n)) \neq n!$ for $n > 1$. –  Matthias Klupsch Nov 22 '11 at 18:47
@Phira, Matthias: OP never said $f(n):=1$, he said that $f(n)=n!$ solves the original recurrence only when $n=1$. –  anon Nov 22 '11 at 18:51
@howdy You got $f(n)!=f(n!)$, why did you conclude that $f(x)=n!$ is a solution? –  N. S. Nov 22 '11 at 19:18
There is a claim for a holomorphic function h such that $\small h \circ h (x)= x!$, such that that h would satisfy your functional equation, but I do not know, whether this claim actually holds. The preprint is at ils.uec.ac.jp/~dima/PAPERS/2010superfae.pdf The index of papers of the author (D.Kouznetsov) is at ils.uec.ac.jp/~dima/PAPERS , see there, entry 87 –  Gottfried Helms Nov 22 '11 at 19:38

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.

-
Ingenious solution! –  user17090 Nov 22 '11 at 18:51
@howdy Because I don't want to and it wouldn't give the right result. I take two chains and define it in the above way, there is nothing that obligates me to set $f(b_k)=c_k$. Then I take the next two chains and do it again. –  Phira Nov 22 '11 at 19:34
Does this work for every injective function instead of n! ? –  user1708 Nov 22 '11 at 19:48
No, injectivity is neither necessary nor sufficient, note that $n!$ is only injective for strictly positive $n$, but the "pathological" values $0$ and $1$ could be dealt with easily. General criteria are that the "graph" of the function on the right side has to have an even or infinite number of one-sided chains and an even or infinite number of two-sided chains and an even number of cycles of even length. For injective functions, this is equivalent, because nothing else can happen. It is not too hard to see what one needs for other functions, but it is not nice to write down explicitly. –  Phira Nov 22 '11 at 20:00
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.
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$.