Functional Equation Analysis

Question

Given:

$$F(F(n)) = n$$

$$F(F(n + 2) + 2) = n$$

$$F(0) = 1$$

where n is a non-negative integer. $$F(129) = ?$$

How can we solve such kind of functional equations? Is there any simpler approach other than doing iteration over the values manually?

Answer 1

Firstly, I think you had better allow $n$ to be an arbitrary integer, because these equations force the value of $F(n)$ to be negative when $n > 1$.

Secondly, to solve this system of equations, apply $F$ to the second equation, and then appeal to the first equation, to find that $$F(n+2) + 2 = F(n),$$ i.e. that $$F(n+2) = F(n) - 2.$$ This allows us to reduce computing $F$ to the case when either $n = 0$ or $n = 1$. The first case is given to us in the question, namely $F(0) = 1$. For the second case, note that the first equation, with $n = 0$, gives $F(F(0)) = 0,$ i.e. $F(1) = 0$.

Now we can easily compute all values of $F$, and indeed we find that $F$ has a very simple closed form, the derivation of which I leave as an exercise.

The basic idea in the above is the that first equation establishes $F$ as its own inverse, and so this can be used to simplify the second equation.