Problem 1. Consider the set $N=\{1,2,3, \ldots\}$ of natural numbers and the function $f$ : $N \rightarrow N$ that satisfies the following two conditions:

a) $f(f(n))=n$ for all $n \in N$.

b) $f(f(n)+1)=\left\{\begin{array}{cc}n-1, & \text { if } n \text { is even; } \\ n+3, & \text { if } n \text { is odd. }\end{array}\right.$

Determine the value of $f(n)$ for each $n \in N$ by first observing that $f$ is bijective and that, since $f(f(n)+1)$ is never $2$, it must be that $f(1)=2$.
Solution:

By condition a), it is obvious that $f$ is bijective. And, as condition b) shows that $f(f(n)+1)$ is never 2, it must be that 2 is the image of the only element that is not of the form $f(n)+1$, that is, of 1: $f(1)=2$. And again by a), $f(2)=1$.

We will prove, by induction on $n$, that

$$
f(n)=\left\{\begin{array}{l}
n+1 \text { if } n \text { is odd } \\
n-1 \text { if } n \text { is even }
\end{array}\right.
$$

For $n=1$ and for $n=2$ this has already been seen. Suppose $n>2$.

By the induction hypothesis, we have

$$
f(n-1)=\left\{\begin{array}{l}
n \text { if } n \text { is even } \\
n-2 \text { if } n \text { is odd }
\end{array}\right.
$$

and also

$$
f(n-2)= \begin{cases}n-1 & \text { if } n \text { is odd } \\ n-3 & \text { if } n \text { is even }\end{cases}
$$

Now,

$$
\begin{aligned}
f(n) & =\left\{\begin{array}{l}
f(f(n-2)+1), \text { if } n \text { is odd } \\
f(f(n-1)) \text { if } n \text { is even }
\end{array}\right. \\
& =\left\{\begin{array}{l}
n-2+3=n+1 \text { if } n \text { is odd } \\
n-1 \text { if } n \text { is even }
\end{array}\right.
\end{aligned}
$$