**Problem**: (1992 Putnam - A1) Prove that $ f(n) = 1-n $ is the only integer-valued function defined on the integers that satisfies the following conditions.

(i) $ f(f(n)) = n $;

(ii) $ f(f(n+2)+2) = n $;

(iii) $ f(0) = 1 $.

**Solution**: We will use induction to prove the claim for $ -k \le n \le k+1 $ where $ k $ is a nonnegative integer.

Base Case: $ k = 0 \Rightarrow f(0) = 1, f(1) = 0 $ which are true from (iii) and (i).

Induction Step: Assume that $ f(n) = 1-n $ for $ -k \le n \le k+1 $.

Then $ f(k+2) = f(f(-k+1)+2) = -k-1 = 1-(k+2) $ by our induction hypothesis and (ii). Also, $ f(-(k+1)) = k+2 = 1-(-(k+1)) $ by (i), completing the induction.

Hence $ f(n) = 1-n $ for all integers. QED.

--------------------

Comment: Functional equations over the integers are not usually too hard to handle; induction is usually a good way to handle them, strong induction in particular. Most of the time you just need to find out what set to induct on, in this case $ [-k,k+1] $.

--------------------

Practice Problem: Find all functions $ f: \mathbb{N} \rightarrow \mathbb{N} $ such that

(1) $ f(f(n)+n) = f(n) $;

(2) There exists a $ n_0 $ such that $ f(n_0) = 1 $.

well if f(n_0) = 1 it follows

ReplyDeletef(1 + n_0) = 1

and so f(k) = 1 for k \ge n_0

let f(1) = k, then

f( k + 1) = k

f( 2k + 1) = k

...

f(mk + 1) = k

but some m will have mk + 1 \ge n_0 so k = 1

QED lol