Iterated Function Generalisation

Intro to Functions

Skip to the next section if you already know about functions.

In maths, a function is an equation, for example '$2x+1$'. The thing that sets functions and equations apart is that functions can be defined '$f(x) = 2x + 1$' and then used later '$f(3) = 2(3) + 1 = 6 + 1 = 7$'. '$f(x)$' is terminology meaning ‘a function called '$f$' which takes a parameter, $x$’, and here ‘3’ is the input for the parameter '$x$'. Also, the name does not necessarily have to be '$f$' and the parameter does not necessarily have to be '$x$'. The most common names are '$f$' and '$g$'; and '$x$' is the most common parameter.

Some examples are:

$f(x) = 3x + 5$, $f(3) = 3(3) + 5 = 9 + 5 = 14$

$g(q) = q^{2} - 1$, $g(7) = 7^{2} - 1 = 49 - 1 = 48$

$h(y) = 2y^{3}$, $h(10) = 2(10^{3}) = 2(1000) = 2000$

Iterating Functions

Skip to the next section if you already know what '$f(f(f(x)))$', '$f(g(x))$' and '$f^{-1}(x)$' mean.

Say that $f(x) = 5x$ and $g(x) = x + 3$, then you can nest the functions by inputting one to the other, eg. $f(g(x))$ is equal to $5g(x)$, which in turn can be simplified to $5(x + 3)$, which finally becomes $5x + 15$. You can also nest functions three times, and more. For example:

$f(x) = x^{2}$

$g(x) = x + 1$

$h(x) = 2x$

$g(h(f(x))) = h(f(x)) + 1 = 2f(x) + 1 = 2x^{2} + 1$

It’s also possible to nest a function with itself instead of other functions. If $f(x) = 2x + 1$, then $f(f(x)) = 2f(x) + 1 = 2(2x + 1) + 1 = 4x + 2 + 1 = 4x + 3$; and $f(f(f(x)) = 2f(f(x)) + 1 = 2(4x + 3) + 1 = 8x + 6 + 1 = 8x + 7$.

Finally there is the inverse. If $f(x) = 3x - 1$, then the inverse is defined as the function that, when nested with $f(x)$, would simplify to $x$. In this case the inverse is $(x + 1)/3$. (The inverse is written as $f^{-1}(x)$.) To prove it: $f(f^{-1}(x)) = 3f^{-1}(x) - 1 = 3((x + 1)/3) - 1 = (x + 1) - 1 = x$.

Nesting Shorthand

I use '$f^{2}(x)$' to mean $f(f(x))$. This is unofficial and if you were to ask a maths examiner to simplify '$f^{2}(x)$' then they would say, ‘You have the 2 in the wrong place!’, swap it to '$f(x)^{2}$' and then simplify that by simply squaring whatever equation $f(x)$ represents. The reason I shorten it like this is because:

1. Then you can write '$f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))$' as '$f^{17}(x)$' and

2. You’ll see.

Also normally '$f(f(f(x)))$' is written '$fff(x)$', without the extra brackets, but I feel like that just distracts from the actual meaning and can be sort of confusing.

Generalisation Time!

So after doing that, then I found that it was quite fun (at least for a complete maths geek like myself) to work out puzzles like the following:

$f(x) = 2x + 1$

$f^{3}(x) = \text{?}$

My solution:

$f^{3}(x) = 2(2(2x + 1) + 1) + 1 = 2(4x + 3) + 1 = 8x + 7$

And then I wondered, why not do it in reverse? So of course then I attempted:

$f^{2}(x) = 4x + 9$

$f(x) = \text{?}$

My solution:

If $f(x) = ax + b$, then $f^{2}(x) = a(ax + b) + b$. This can be simplified to $a^{2}x + ab + b = 4x + 9$. Notice that there is only one term with $x$ in it on both sides of the equation. Therefore, the coefficients for each of those terms are equal to each other. Therefore, $a^{2} = 4$, and finally $a = 2$. Next, subtract out the two $4x$ terms to leave $ab + b = 9$. $a$ is equal to 2, so this becomes $2b + b = 9$, $3b = 9$, $b = 3$. Therefore $a = 2$ and $b = 3$. Substitute into the original equation: $f(x) = 2x + 3$.

Notice that my solution is much longer for the reverse progress — it is much more complicated.

Next, I thought, why does it have to be integers? Why can’t I have $f^{1/2}(x)$? So I made that a thing, and defined $f^{1/2}(f^{1/2}(x))$ to equal $f^{1}(x)$ (By this time I had gotten into the habit of using '$f^{1}(x)$' to mean '$f(x)$', because they are functionally identical — just like $1(1x + 0)^{1} - 0$ and $x$).

After that then I started challenging myself not just to find $f^{1/3}(x)$ or $f^{-5}(x)$, but to find the general $f^{q}(x)$. Here is one such challenge:

$f(x) = 3x + 2$

$f^{q}(x) = \text{?}$

My solution:

Gather info first. $f^{2}(x) = 3(3x + 2) + 2 = 9x + 8$; $f^{3}(x) = 3(9x + 8) + 2 = 27x + 26$; $f^{4}(x) = 3(27x + 26) + 2 = 81x + 80$. For each addition of 1 to $q$, the coefficient of $x$ is multiplied by 3. This is because each time there is $3(\text{[x term]} + \text{[const.]}) + \text{[const.]}$ and since the constants can never be combined with the $x$ term, if your sole aim is to find the new $x$ term, then the equation simplifies to $3\text{[x term]}$. The constant is always 1 less than the $x$ term, and this also has a reason. If the $x$ term’s coefficient is $c$ and the old constant is already $c - 1$, then this substitutes to $3(cx + c - 1) + 2$, which becomes $3cx + 3c - 3 + 2$. Finally this turns into $3cx + 3c - 1$. The $x$ term has been multiplied by 3 (like before) and the constant is still one less than the $x$ term’s coefficient. With this information, we can justify the recognition of the $x$ term’s coefficient in $f^{2}(x)$ as $3^{2}$ and the recognition of its constant as $3^{2} - 1$. And now I think I see a general formula: $3^{q}x + 3^{q} - 1$. I feel that I made some mistakes here, and that this is not as formal as I would have hoped, but it got the correct answer.

Test:

Let’s work out $f^{-1}(x)$ in two ways. One from the general formula, and one where we ‘flip $f^{1}(x)$ inside out’. The second is the normal method I would use because it is faster as it does not need the working out above.

First, the general formula. Substituting gives $3^{-1}x + 3^{-1} - 1$. This simplifies to $x/3 + 1/3 - 1$, which simplifies one last time to give $x/3 - 2/3$.

Next, the ‘inside out’ method. $f(x) = 3x + 2$, so first we need to subtract the two: $(f(x)) - 2$. This simplifies to $3x$, so that gets rid of the constant. Next, divide by three to give $((f(x)) - 2)/3 = x$. This is correct because it simplifies to $x = x$ when you pop the $f(x)$. Therefore, $f^{-1}(x) = (x - 2)/3$.

Let’s compare the two. $x/3 - 2/3$ and $(x - 2)/3$ may look different at a glance, but if we pop the brackets in the second equation and distribute the $1/3$, then it makes: $x/3 - 2/3$. Exactly the same! I think this works.

This means we can mess around and stick in any old number to the formula, like $f^{7}(x) = 3^{7}x + 3^{7} - 1 = 2187x + 2186$. Or even, for the truly mad (like me), the imaginary number $i$, (equal to $\sqrt{-1}$). This results in approximately deep breath $(0.45483242282661 + 0.89057704166775i)x + (0.54516757717339 + 0.89057704166775i)$. (I used a calculator for that one — sad).

Paradoxes

And, there is an inverse to the operation that changes $f^{1}(x)$ into $f^{q}(x)$. It’s probably nigh-on impossible, but I’m going to attempt to use this inverse on $f^{q}(x) = 2x^{q} + q^{2}$. Oh wait. I can just substitute. That was disappointing. I was hoping for something really difficult. Oh well. $2x + 1$. Sad.

Wait. If I can do that, then I suppose the general function will work for $q = 2$ as well. Let’s test that. It’s $4x + 3$ the normal way and the general function says that it’s… $2x^{2} + 4$?! I guess the general function is paradoxical. Dis-ap-point-ing! Oh well.

Now for something very interesting. Here’s another puzzle:

$f^{1}(x) = x^{2} + 1$

$f^{2}(x) = \text{?}$

My solution:

$f^{1}(x)^{2} + 1 = (x^{2} + 1)^{2} + 1 = x^{4} + 2x^{2} + 1 + 1 = x^{4} + 2x^{2} + 2$.

Nothing problematic yet, but now…

$f^{1/2}(x) = \text{?}$

My solution:

I don’t have one, and I can prove that a new axiom must be added to mathematics to give an answer to this equation. Here’s my reasoning:

$f^{1}(x) = x^{2} + 1$

$f^{2}(x) = x^{4} + 2x^{2} + 2$

$f^{3}(x) = x^{8} + 4x^{6} + 8x^{4} + 8x^{2} + 5$

$f^{4}(x) = x^{16} + 8x^{14} + 32x^{12} + 80x^{10} + 138x^{8} + 168 x^{6} + 144x^{4} + 80x^{2} + 26$

Count the terms in each equation: 2, 3, 5, 9. These can be represented by the general formula $2^{q - 1} + 1$.

Now this means that the number of terms in $f^{1/2}(x)$ must be $2^{1/2 - 1} + 1 = 2^{-1/2} + 1 = 1/\sqrt{2} - 1$. You can’t have a number of terms that isn’t an integer! Finally, I did skip over something earlier: I jumped to a conclusion that 2, 3, 5, 9 would continue 17, 33, 65, 129… one way and …1.5, 1.25, 1.125 the other. So I will now prove that the general formula $2^{q - 1} + 1$ is correct. When squaring the equation, there will be two terms in the working out: $x^{m}(x^{m} + \text{?}x^{m-2} \ldots + \text{?})$ and $\text{?}(x^{m} + \text{?}x^{m-2} \ldots + \text{?})$. The first will simplify to $x^{2m} + \text{?}x^{2m - 2} \ldots + \text{?}x^{m}$, which contains a term for every even number between (inclusive) $2m$ and $m$. The second will simplify to $\text{?}x^{m} + \text{?}x^{m - 2} \ldots + \text{?}x^{0}$, which contains a term for every even number between (inclusive) $m$ and 0. When combined, these two terms simplify to an equation which contains a term for every even number between $2m$ and 0. If the previous function already has 1 more than a power of 2 terms, then this one will also have 1 more than a power of 2 terms. Hopefully that clears that up.

Oh, and one last thing: what does happen if you try to solve it?

$ax^{b} + [\text{exactly } 1/\sqrt{2} - 3 \text{ terms (which just so happens to be a negative amount)}] + c = f^{1/2}(x)$

You end up with a negative amount of terms in the centre. This is a mathematical impossibility — and therefore the equation does not exist. Although, we do know that the first term must actually be '$x$' — $a$ and $b$ are both 1! The reason for this is that for each addition of 1 to $q$, the exponent of the first term doubles, and it NEVER gains a coefficient. So in reverse, it still will never gain a coefficient, and the exponent will be halved, to 1. And also, '$c$' gets squared then raised by one for each time that $q$ is raised by one. It’s just getting the function $x^{2} + 1$ applied to it! The reason for this is:

In the equation, when the constant is multiplied by something else as a result of the squaring, the new term does not contribute to the new constant. Only when the constant is multiplied by itself will the result contribute to the new constant. And this only happens once, so the squaring simply squares the constant. Then, on the end, there is a ‘+1’, so the constant gets one added to it. So when $q$ gets lowered by one, we apply the inverse of $f(x)$ to it, namely $f^{-1}(x) = \sqrt{x - 1}$. In this case, after substituting we are left with $\sqrt{1 - 1}$. This is equal to 0 exactly — the constant vanishes! Now it seems a little more plausible that there could be $1/\sqrt{2} - 1$ terms, but that number is still negative, so the paradox remains.

The Axioms & Outro

So, in conclusion, the axioms for this system are:

$f^{a}(f^{b}(x)) = f^{a+b}(x)$

$f^{0}(x) = x$

I hope that you enjoyed this journey to the outskirts of the mathematical land (or at least as far as I’m daring to go, it’s not happening infinity! I’m watching you). I will be back with another one in a few weeks or so at most. See you then.

No. I already told you. Not happening. Sorry infinity. Now can you please go so that I can finish this blog post?

No?! That’s a terrible answer. If you don’t leave soon then I’m subtracting infinity from you.

I’m not kidding, why do you look so carefree?

Ok, that’s it! $\infty - \infty = \infty$.

Oh, that old trick again. Fine! You can stay. Just let me finish this post, because it’s long as it is!

[sighing] Thank you.

So, see you then (but not you infinity, please leave before I lose my temper again).