Part 3:  Iterated Functions Given any two binary operations a(x,y) and b(x,y), suppose there is a function f such that For any set of such functions, define the auxiliary functions It's easy to see that u and v are "conjugates", in the sense that Slightly less obvious is the fact that the nth compositions of u(x) and v(x), denoted by un(x) and vn(x) respectively, are also conjugates, i.e., This identity is sometimes useful in simplifying computations. To illustrate, consider the case a(x,y) = xy, b(x,y) = x + y, f(x) = ln(x).  Here the auxiliary functions are Taking an initial x value of 10, the first few iterations of u(x) are 10.000000,  23.025851,  72.223287,  309.098522 Beginning with an initial x value of f(10) = 2.302585 the first few iterations of v(x) are 2.302585,  3.136617,  4.279762,  5.733660 Comparing these sequences of iterates, we see that the function f maps from one to the other.  For example, we have f(309.098522) = 5.733660.  More generally, if we take f(x) = logb(x) for any base b, and define the auxiliary functions then the nth iterates of these functions, denoted by un(x) and vn(x), are related by the equation The logarithm has a unique inverse (although the log itself is multi-valued for negative arguments), so this allows us to give un(x) explicitly in terms of vn(logb(x)) as In general, any function f(x) possessing an "addition rule" can be adapted to this process.  A few examples are summarized below. This procedure can also be applied to additive number-theoretic functions.  For example, consider the case where x(x) is the "sum-of-prime-factors" function.  In this case the auxiliary functions are Beginning with an initial value of 10, the first few iterations of H are 10,  70,  980,  22540,  1036840 Beginning with an initial value of x(10) = 7, the first few iterations of G give 7,  14,  23,  46,  71 and we can verify that x(1036840) = 71. Proposition 12:  Letting Hn(N) and Gn(N) denote the nth iterations of the functions H(N) = Nx(N) and G(N) = N + x(N), we have and for any integer m. Proof:  It's easy to show by induction that for any integer a.  Now suppose that Then we have The quantity in the square brackets equals Gk(x(m)), as can be seen by setting a = x(m) in the earlier expression for Gk(a), so the proof is completed by induction. à Corollary 12-1:  For any non-negative integers n and m we have Proof:  By Proposition 12 we have and Combining these two equations gives Rearranging terms gives The right hand side equals zero, so the left side also equals zero for any non-negative integer k. à Table of Contents