Infinite Recursion And It's Limits

Posted by Bedaywi, Mark on December 24, 2019

Read Time: 3 Minutes

After playing with tetration, I started to wonder how we can solve equations of the form:
x x = b for some b

To approach this problem we can look to the properties of infinite recursion. Generally, we can represent a function being applied with itself as so:
lim n f n ( x ) = f(f(f(f(f(f(f(f(... = k for some arbitary x in f's domain

We can take both sides as input to f. Notice how the left side stays the same, since one added to infinity is still infinity. Since both f(k) and k can be represented using infinite recursion f(k) and k must be equal.
f(f(f(f(f(f(f(f(... = k f(f(f(f(f(f(f(f(... = f ( k ) f ( k ) = k

This means we can solve any equation of the form f(x)=x by computing the value of fn(x) for some large n. Note the choice of x is important in some cases. Trivially, if x=k then the identity always applies. Most of the time the choice of x is arbitrary and infinite recursion eventually reaches a limit. In cases where a solution doesn't exist the function cannot ever approach a value for any choice of x. Lastly, some functions have unstable solutions, where only a specific set of starting x values result in the recursion reaching a limit. We can demonstate this with these two simple functions:
f ( x ) = x + 1 3 g ( x ) = x 2 + 1 3
We can see that starting at any value for x would always lead to f(x) approaching 0.5, but for g(x) x has to be between -1 and 1 to approach one of the solutions 0.38196, to find the second solution x must be equal to 3+52 exactly for it to approach it. The second function is more unstable and the second solution is the most unstable.

We can apply this technique to more interesting functions like f(x)=cos(x). Finding cos(cos(cos(cos(cos(... for some arbitrary starting point leads us to the solution x=0.73908.

Going back to the original question consider the function:
f ( x ) = log 1 b x for some constant b
Doing some rearranging we can turn this into our original problem:
log 1 b x = x 1 b x = x 1 b = x 1 x b = 1 x 1 x

This means that the limit lim n f n ( x ) gives us the reciprocal of the solution to x x = b for the b in the function. In practice we need to take the absolute value of x to ensure that x remains in the functions domain, this is when we only care about real solutions. This is a much better way to find the solution compared to Newton's method as only one logarithm function is needed. Furthermore, I've found that the values converge to the solution faster when starting at the same values.

Using this knowledge, we can write some code that solves equations like this for us:

def solve(b, time=500, accuracy=100):
    #Solves x^x=b
    from math import log
    import decimal
    decimal.getcontext().prec = accuracy
    x = decimal.Decimal(2) #this value is arbitrary
    for _ in range(time):
        x = decimal.Decimal(log(abs(x), 1/b))
    return 1/x

As a result of this we can now not only solve some tetration equations faster but also we have a new tool to calculate numerical solutions to equations and a new way of thinking of functions. Nice!