Exercise 15. For a function $f$ and $n$ a strictly positive integer, we denote $f^{n}$ the $n$-th composition of $f$ defined by $f^{n}=f \circ f \circ \ldots \circ f$ where $f$ appears $n$ times on the right-hand side.

Find all functions $f: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*}$ such that

$$
f^{f(n)}(m)+m n=f(m) f(n)
$$

for all $m, n \in \mathbb{N}^{*}$.
## Solution to Exercise 15

For $m=n$, we find that $f(m)^{2}=f^{f(m)}(m)+m^{2}>m^{2}$, which gives $f(m)>m$ since $f(m)$ is positive, and thus, as $f(m)$ is an integer, $f(m) \geqslant m+1$. By a simple induction, we find that for all positive integers $k, m$, $f^{k}(m) \geqslant m+k$.

But we notice that apart from the first term in the statement, the rest is symmetric in $m$ and $n$, and we can write that for all $m, n>0$,

$$
f^{f(n)}(m)+m n=f(m) f(n)=f^{f(m)}(n)+n m
$$

and thus $f^{f(n)}(m)=f^{f(m)}(n)$. We want to use the fact that we are dealing with a composition, so we set $n=f(a)$ so that $f^{f(m)}(n)=f^{f(m)+1}(a)$. By evaluating the previous equation with $a=m$, we have

$$
f^{f(m)+1}(m)=f^{f(f(m))}(m)
$$

But this implies that $f(f(m))=f(m)+1$. Indeed, otherwise, let $\alpha=\min (f(f(m)), f(m)+1)$ and $k=\max (f(f(m)), f(m)+1)-\alpha>0$ so that the equation reads $f^{k}\left(f^{\alpha}(m)\right)=f^{\alpha}(m)$. But this is absurd because $f^{k}\left(f^{\alpha}(m)\right) \geqslant f^{\alpha}(m)+k>f^{\alpha}(m)$.

We deduce that for all $m \in \mathbb{N}^{*} f(f(m))=f(m)+1$. By a simple induction, for all $k \geqslant 1$, $f^{k}(m)=f(m)+k-1$. Thus the equation in the statement gives for all $m, n \in \mathbb{N}^{*}$,

$$
f(m)+f(n)-1+m n=f(m) f(n)
$$

If $n=m$, we obtain an equation simply linking $f(n)$ and $n$:

$$
2 f(n)+n^{2}-1=f(n)^{2}
$$

This is a quadratic equation that can be factored, for example, as $(f(n)-1)^{2}=n^{2}$, so $f(n)=n+1$ since $f(n)$ is strictly positive.

Conversely, if $f(n)=n+1$ for all $n$, then we can write for all $m, n$:

$$
f^{f(n)}(m)+m n=m+f(n)+m n=m n+m+n+1=(m+1)(n+1)=f(m) f(n)
$$

and this function is indeed a solution to the equation in the statement.

Comment from the graders: Students who solved the problem all have a solution studying the antecedents of the smallest element in the image of $f$. It is excellent to have been able to adapt this kind of argument to a functional equation. This was indeed where the difficulty lay, and some subtleties of the argument escaped the vigilance of some students. Moreover, several students did not hesitate to propose their proof of elementary properties of $f$, which is very good to practice: the injectivity of $f$, the fact that $1$ is not reached, the symmetry of the functional equation in $m$ and $n$.