Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
How about F(n) = 1-n ? –  user17762 Jan 29 '11 at 6:35
    
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$ –  user17762 Jan 29 '11 at 6:42
    
@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. –  Matt E Jan 29 '11 at 22:15
    
@Matt E: Right. I wrote it in a hurry without thinking about it. Sorry for the misleading comment. –  user17762 Jan 29 '11 at 22:45
    
I believe this problem was on the 1992 Putnam Exam. There is a version of a solution here: problemchain.wordpress.com/2010/04/30/putnam-1992-ffn-n –  AnonymousCoward Jan 30 '11 at 0:16

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.