Solving functional equations programmatically

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 programmatically? My programming language of choice is Python.

Answer 1

Functional equations, in their most general terms, are really really hard. It is no coincidence that pretty much every international mathematics competition features one of them, usually looking about as innocent as the one you've written. The methods of solving them vary from plain induction to infinite-dimensional Banach space analysis and a generic programming approach to solving them is very unlikely.

In this particular case, here's a straight-forward approach:

Suppose for any two integers m, n we have F(m) = F(n) = k. But then m = F(F(m)) = F(k) = F(F(n)) = n : therefore m = n and F never takes the same value on two different inputs. But we know that F(F(n)) = n = F(F(n+2)+2) - therefore F(n) and F(n+2)+2 must be the same number - which is to say, F(n+2) == F(n) - 2 == F(n-2) - 4 = ... . Now we know F(0) = 1, so F(1) = F(F(0)) = 0. But then F(129) = F(127) - 2 = F(125) - 4 = ... = F(1) - 128 = -128

So there is your solution - but a mechanical algorithm for solving any variation just doesn't exist.

Answer 2

Based on what @ivancho and @aaronasterling have said, I have been able to write this program that should do the trick:

def f(n):
    if not n:
        return 1
    else:
        return f(n-2)-2

>>> f(4)
-3

Comment if this is not what you're after