1
$\begingroup$

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?

  • 0
    I believe this problem was on the 1992 Putnam Exam. There is a version of a solution here: http://problemchain.wordpress.com/2010/04/30/putnam-1992-ffn-n/2011-01-30

1 Answers 1

6

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.