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