CODEWITHSUNDEEP
pythonfunctionmath
Sharathiitr
Sharathiitr

Reputation: 111

Solving functional equations programmatically

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.

Upvotes: 11

Views: 1618

Answers (2)

inspectorG4dget
inspectorG4dget

Reputation: 114035

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

Upvotes: 2

ivancho
ivancho

Reputation: 899

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.

Upvotes: 6

Related Questions