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