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 u_{n}(x) and v_{n}(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) = log_{b}(x) for any base b, and define the auxiliary functions 

_{} 

then the nth iterates of these functions, denoted by u_{n}(x) and v_{n}(x), are related by the equation 

_{} 

The logarithm has a unique inverse (although the log itself is multivalued for negative arguments), so this allows us to give u_{n}(x) explicitly in terms of v_{n}(log_{b}(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 numbertheoretic functions. For example, 
consider the case 

_{} 

where x(x) is the "sumofprimefactors" 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 H_{n}(N) and G_{n}(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 G_{k}(x(m)), as can be seen by setting a = x(m) in the earlier expression for G_{k}(a), so the proof is completed by induction. à 

Corollary 121: For any nonnegative 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 nonnegative integer k. à 
