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

fixed points-functionsiterated-function-system

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.
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 ðŸ™‚

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.}}$$