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