Q:

Show that the function $p(k)=k+(-1)^kc$ is a permutation of the set of all integers

This problem is from the book "Concrete Mathematics (2nd) written by Graham, Knuth and Patashnik"

Show that the function $p(k) = k+(-1)^kc$ is a permutation of the set of all integers, whenever $c$ is an integer.

The author's answers is as follows.

if $p(k)=n$ then $n+c=k+((-1)^k+1)c$ and $((-1)^k+1)$ is even; hence $(-1)^{n+c}=(-1)^k$ and $k=n-(-1)^{n+c}c$, Conversely, this value of $k$ yields $p(k)=n$

I could see the fact $k=n-(-1)^{n+c}c$, but I could not understand the reasoning of the proof. Generally, to prove a function is a permutation of the set all all integers, what do we have to show?

A:

We have to show that it’s a bijection from $\Bbb Z$ onto $\Bbb Z$. The argument shows that for any $n\in\Bbb Z$ we can find a $k\in\Bbb Z$, namely $n-(-1)^{n+c}c$, such that $p(k)=n$; this clearly establishes that $p$ is surjective. It also implicitly establishes that $p$ is injective, since the calculation clearly shows that this $k$ is uniquely determined by $n$. If that part worries you, you can make it explicit. Suppose that $p(k)=p(\ell)=n$; then $(-1)^k=(-1)^{n+c}=(-1)^\ell$ by the argument given in the book, so $k\equiv\ell\pmod2$. But $k+(-1)^kc=n=\ell+(-1)^\ell c$, so
$$k-\ell=c\left((-1)^\ell-(-1)^k\right)=0\;,$$
since $k\equiv\ell\pmod2$, and therefore $k=\ell$ and $p$ is injective.

