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. à