Notation for iterating functions

Question

Is there any well established notation for iterating a function a certain amount of times? What I mean is that, let's say you have a function $f(x)$ that you are iterating a certain amount of times:

$$\underbrace{f(f(f(f(\cdots(x)\cdots))))}_\text{$n$ times}$$

Is there some similar notation to e.g. the $\sum$ symbol if we would be talking about sums?

Answer 1

The usual notation is to write $$ f^n(x) = (\underbrace{f\circ f \circ\dotsb\circ f}_{\text{$n$ times}})(x). $$

The notation is (perhaps) motivated by the observation that many classes of functions (e.g. continuous functions from $\mathbb{R}$ to $\mathbb{R}$ form an algebraic structure, where composition is plays the role of a multiplication operator.

Answer 2

You can use one of $f^n$ and $f^{(n)}$, though both are ambiguous and can be confused with the $n^{\text{th}}$ power or the $n^{\text{th}}$ derivative respectively (or even the rising factorial, though this would quite exceptionally be applied to a function).

Answer 3

As both the $f^n \circ x$ and the $f^{(n)} \circ x$ notations have their own alternate meanings ($f^n \circ x = \displaystyle\prod_{i = 1}^{i = n} (f\circ x)$, $f^{(n)} \circ x = {d^n f\over dx^n}$), that are distinct from function composition / recomposition.

One proposed operator is the recomposition operator, the reuse of the composition ($\circ$) operator.

This way, your case would become $f\overset{n} \circ x$, where $$f\overset{m + 1} \circ = f\overset{m} \circ f = f\circ f\overset{m}\circ$$

This is also, for bijective functions, extensible from $n\in\mathbb N^*$ to $n\in\mathbb Z$ (or even $n\in\mathbb R$).

Let's say we have $f\circ x = f(x) = 2x$: $f\overset 2\circ x = f(f(x)) = 2(2x) = 4x$, which is easily extensible to $\mathbb R_+$: $f\overset r\circ x = 2^r x$.

For the same function $f$, $f\overset{- 1}\circ x = {x\over 2}$, the reverse¹ of $2x$.

And even $f\overset 0\circ x = x$, the identity function.

Other pro of the recomposition proposal is killing the $\sin^{- 1}, \cos^{- 1}, \tan^{- 1}$ problems.

Ex: $\sin^{- 1} = {1\over\sin} = \csc$, while $\sin\overset{- 1}\circ x = \arcsin\circ x \overset 2= x\circ \sin$

Notes:

1. Inverse of $f$: ${1\over f}$. The reverse of $f\circ x$: $f\overset{- 1}\circ x$.
2. Informally / Not so formally, $x\circ f$ ($x$ of $f$) may appear as the reverse of $f\circ x$ ($f$ of $x$).

• I did not work all the domains and images / codomains problems / restrictions. It's always good remembering of doing so, mainly with reversions.
• LaTeX for the operator: \overset n \circ, or even \overset{n}\circ.