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
    How about F(n) = 1-n ?2011-01-29
  • 0
    Assume nice things bout F, like 1-1 and onto. $F(F(n)) = n \Rightarrow F(n) = F^{-1}(n)$. and from second equation $F(n+2) + 2 = F(n)$ And from first equation you get $F(1) = 0$. Do a telescopic summation to get the result as $F(n) = 1-n$2011-01-29
  • 0
    @Sivaram: Dear Sivaram, You don't need to *assume* that $F$ is 1-1 and onto; the first equation establishes that $F$ is its own inverse, so that $F$ is *necessarily* 1-1 and onto.2011-01-29
  • 0
    @Matt E: Right. I wrote it in a hurry without thinking about it. Sorry for the misleading comment.2011-01-29
  • 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.