A problem in Putnam Competition 1992(?). The question asked:

Prove that, the only solution of the system of functional equation with respect to $f:\mathbb Z\to\mathbb Z$:$$ \begin{cases} f(f(n))=n\\ f(f(n+2)+2)=n\\ f(0)=1 \end{cases} $$ is $f(n)=1-n$.

I know that the usual way is to construct another solution, and show that the difference between the two solutions is zero. But I want to use equivalence condition this time. (i.e. Prove that the system is equivalent to say that $f(n)=1-n$).

Now, we have $$f(f(n))=f(f(n+2)+2)$$ Take $f$ on both sides. $$f(f(f(n)))=f(f(f(n+2)+2))$$ Again by the first equation, $$f(n)=f(n+2)+2$$ And another useful thing is that, $$f(1)=f(f(0))=0$$

So, the original system is equivalent to say the recurrent relation $$ \begin{cases} f(n)=f(n+2)+2\\ f(0)=1\\ f(1)=0 \end{cases} $$ The sequence-like function satisfying above is unique, trivially (as for all integers, we could find an unique image of it). So our proof is actually done already as $f(n)=1-n$ is simply a solution. Q.E.D.

In my proof, I used a lot of equivalence condition. I know that my proof is valid if the conditions are actually equivalent. I think so for myself, but I want peer reviews also. Thanks in advance.


Your proof is correct, well done! If you wanted to, you could show that from your last recurrence relation $$ \begin{cases} f(n)=f(n+2)+2\\ f(0)=1\\ f(1)=0 \end{cases} $$ yields a unique solution through a simple induction as well.


Note that $f$ is an injective function. To show this, suppose $f(m)=f(n)$ for some $m,n\in\mathbb{Z}$. Therefore, $$m=f\big(f(m)\big)=f\big(f(n)\big)=n\,.$$

Now, the condition $f\big(f(n+2)+2\big)=n$ comes into play. Observe that $$f\big(f(n)\big)=n=f\big(f(n+2)+2\big)\,.$$ By injectivity, $$f(n)=f(n+2)+2\text{ for all }n\in\mathbb{Z}\,.\tag{*}$$

Since $f(0)=1$, we conclude by induction on $n$ that $$f(2n)=1-2n\text{ for every }n\in\mathbb{Z}_{\geq 0}\,.$$ We can also induct the other way around, using (*), again to show that $$f(2n)=1-2n\text{ for every }n\in\mathbb{Z}_{<0}\,.$$ This shows that $f(n)=1-n$ for all even integers $n$. Now, let $n$ be an odd integer. We get that $$f\big(f(n)\big)=n=1-(1-n)=f(1-n)\,,$$ as $1-n$ is an even integer. Therefore, $$f(n)=1-n\text{ for each odd integer }n$$ as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.