An Induction to Functional Equations

The RHS is $n$ , which ranges through the whole set of integers, hence $f(m)$ is surjective $\forall m\in\mathbb Z$ .

$\displaystyle f(x)=f(y), x,y\in\mathbb Z\implies f(f(x)+1)=f(f(y)+1)$

$\displaystyle \implies x=y\implies f(m)\text{ is injective}, \forall m\in\mathbb Z$

Let $P(n)$ be the statement $f(f(n)+1)=n$ .

Let $f(n)=m$ . We know that $m$ ranges through the whole set of integers $\mathbb Z$ .

$f(m+1)=n$

$\implies f(f(m+1))=f(n)=m, \forall m\in\mathbb Z\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(1)$

$P(m)\implies f(f(m)+1)=m\stackrel{(1)}=f(f(m+1))$

\stackrel{\text{injective}}\implies f(m)+1=f(m+1), \forall m\in\mathbb Z

The only functions $f:\mathbb Z\to \mathbb Z$ that could satisfy this property are of the form $f(n)=n+c$ for some integer $c$ .

When $n$ goes up by $1$ , the function also goes up by $1$ , and vice versa. Knowing this, it is not difficult to see why my last claim is true.

But such a function would in our case require $c=-\frac{1}{2}$ . The codomain of our function is $\mathbb Z$ , which makes this impossible, hence there are no function-solutions at all. $\square$