$ f(f(f(x))) = x $ with $ f(x) \ne x $ and $ f(f(x)) \ne x$

Question

I recently came to wonder if there are function that, when applied, iteratively, become a fix point, but only after a certain amount of iteration.

Formally, let's define the following: $f_1(x) = g(x)$, $f_n(x) = g(f_{n-1}(x))$

Now I'm generally looking for any $f_k$ with $f_k(x) = x$, and $f_j(x) \neq x, \forall j\ |\ 0<j< k$. In general, this is easy if you have a "combined" function (sorry I don't know the proper name here) with multiple "ifs".

However, I would like to constraint $g(x)$ to be a function without any "ifs" and without modulo arithmetic.

So far, I've managed to solve this for $f_2$ and $f_4$:

• $f_2$: $g(x) = -x$
• $f_4$: $g(x) = x\cdot i$

NB: At the time of writing this I noticed that $f_2$ and $f_4$ break if x = 0

Now I would like to find a solution for $f_3$, or, in fact, for an $f_k$, or a proof that this isn't possible.

Unfortunately I don't really know where to start my research at or if this is even possible. So I thought I'd ask the MathExchange community and see if we get somewhere :)

Answer 1

For $f_3$ you could consider $$f(x)=1-\frac1x=\frac{x-1}{x}$$ for a suitable domain. Because then $$ff(x)=\frac{\frac{x-1}{x}-1}{\frac{x-1}{x}}=\frac{1}{1-x}$$ And then $$fff(x)=\frac{1}{1-\frac{x-1}{x}}=x$$

Answer 2

Another function:

$$ f(x)=\frac{x+3}{-x-2} $$

You get

$$ f(f(x))=\frac{-2x-3}{x+1}\,,\qquad f(f(f(x)))=x. $$

Remark: There are infinitely many functions of that kind. For example

$$ f(x)=\frac{x-1}{3x-2},\qquad f(x)=\frac{7x-3}{19x-8},\qquad \text{etc.} $$

We can find them very easily. Let

$$ f(x)=\frac{Ax+B}{Cx+D},\qquad A,B,C,D\in\mathbb R,\ AD-BC\neq 0. $$

We compose it with itself twice and we get

$$ f(f(f(x)))=\frac{\left(A^3+2ABC+BCD\right)x+A^2B+ABD+B^2C+BD^2}{\left(A^2C+BC^2+ACD+CD^2\right)x+ABC+2BCD+D^3}=\frac{1x+0}{0x+1}\,. $$

Now we solve the system of four equations:

\begin{align*} A^3+2ABC+BCD&=1\\ A^2B+ABD+B^2C+BD^2&=0\\ A^2C+BC^2+ACD+CD^2&=0\\ ABC+2BCD+D^3&=1. \end{align*}

Suppose $A,B,C,D$ are nonzero real numbers. Then the system has infinitely many solutions in the form:

$$ D=-A-1,\quad C=\frac{-A^2-A-1}B $$ and $A,B$ are set arbitrarily.

Remark 2:

The previous procedure is not effective for solving the equation $f_k(x)=x$ with $k\geq 4$ due to larger systems of nonlinear equations. It is better to look at the problem through a special difference equation

$$ x_{n+1}=\frac{Ax_n+B}{Cx_n+D}\,,\qquad C\neq 0,\quad AD-BC\neq 0, $$

see Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492. I will only mention the part of the article that is related to our problem. We will deal with the simpler form of the equation

$$ x_{n+1}=A-\frac{B}{x_n}\,. $$

Setting $x_n=y_{n+1}/y_n$ we get

$$ y_{n+2}-Ay_{n+1}+By_n=0 $$

which is a linear difference equation of the second order with constant coefficients. It can be solved using a characteristic equation

$$ r^2-Ar+B=0. $$

Let $A^2-4B<0$. Then the characteristic equation has two complex roots:

$$ r_{1,2}=\sqrt B\left(\cos\theta\pm\mathrm i\,\sin\theta\right) $$ where $\theta$ satisfies $\cos\theta=A/(2\sqrt B)$ and $0<\theta<\pi$.

Let us assume that

$$ \frac{\theta}{\pi}=\frac pq\,,\qquad \text{$p$ and $q$ are coprime.} $$

Under these conditions, the sequence $x_n$ contains only $q$ distinct terms $x_1,x_2,\dots,x_q$ which repeat indefinitely in this order, i.e. $x_{q+j}=x_j$, $j=1,\dots,q$, see the AMM article. If we define

$$ f(x)=A-\frac Bx $$

we can express the previous conclusion as $f_q(x)=x$.

Reversely, $f_k(x)=x$, if

$$ r_{1,2}=\cos\frac{\pi}{k}\pm\mathrm i\,\sin\frac{\pi}{k}\,. $$

The characteristic equation is in the form

$$ r^2-\left(2\cos\frac{\pi}k\right)\cdot r+1=0. $$

Thus $A=2\cos\frac{\pi}k$, $B=1$. We can conclude

$$ \color{red}{\boldsymbol{f(x)=2\cos\frac{\pi}k-\frac 1x\qquad\Rightarrow\qquad f_k(x)=x,\quad k\geq 2.}} $$