Self-documenting Iterations


Given function $f(x),$ $f:\space D\rightarrow R,$ with the range $R$ being a subset if the domain $D,$ $R\subset D,$ we may form a composition $f^{(2)}(x)=f(f(x)),$ and then continue $f^{(3)}(x)=f(f^{(2)}(x)),$ ..., $f^{(4)}(x)=f(f^{(3)}(x)).$

Set $f^{(1)}(x)=f(x)$ and define $f^{(n+1)}(x)=f(f^{(n)}(x)),$ for $n\gt 0.$ Functions $f^{(n)}(x)$ are known as the iterates of function $f(x).$ It may appear rather natural to expect that the iterates could be defined equally well by $f^{(n+1)}(x)=f^{(n)}(f(x));$ but how obvious is that?

For some functions $f,$ the iterates accept a form that reveals, i.e. makes explicit, their position in the sequence of the iterates, for other functions not such form exists. $f(x)=x+1$ is the function of the former kind $(f^{(n)}(x)=x+n,$ $n\gt 0),$ $f(x)=\sin x$ of the latter.


Let $\displaystyle f(x)=\frac{x}{\sqrt{1+x^2}}.$ Find $f^{(99)}(1).$




I'll prove by induction that $\displaystyle f^{(n)}(x)=\frac{x}{\sqrt{1+nx^2}},$ making the iterates self-documenting.

For $n=1,$ that is just a definition. Assume, $\displaystyle f^{(k)}(x)=\frac{x}{\sqrt{1+kx^2}},$ for some $k\gt 0,$ and compute

$\begin{align}\displaystyle f^{(k+1)} &= f(f^{(k)}(x)) \\ &=\frac{x/\sqrt{1+kx^2}}{\sqrt{1+x^{2}/(1+kx^{2})}} \\ &=\frac{x}{\sqrt{(1+kx^{2})+x^{2}}} \\ &=\frac{x}{\sqrt{1+(k+1)x^2}}. \end{align}$

To solve the problem, set $x=1:$ $\displaystyle f^{(99)}(1)=\frac{1}{\sqrt{1+99\cdot 1^2}}=\frac{1}{10}.$


One extension of the above problem is natural: $\displaystyle f(x)=\frac{x}{\sqrt[t]{1+x^t}}.$ What other examples of self-documenting iterates can you think of?


This is a problem from the 2009 Chinese Mathematics Competition [Xiong Bin, p 17-18].


  1. Xiong Bin, Lee Peng Yee, Mathematical Olympiads in China (2009-2010). Problems and Solutions, World Scientific, 2013

|Contact| |Front page| |Contents| |Algebra| |Induction|

Copyright © 1996-2018 Alexander Bogomolny