Note that for whatever $k$, we have the following: If $|i-j| = 1$, then $|f(i)-f(j)| \le 1$. Because $f$ is a bijection, $f(i) \neq f(j)$, so $|f(i)-f(j)| = 1$ whenever $|i-j| = 1$. Now, note that if $f(x)$ satisfies the property, then $g(x) = f(x)+c$ also satisfies the property, and vice versa. So let $f(0) = 0$ (by choosing $c = -f(0)$). Also note that if $f(x)$ satisfies the property, then $g(x) = -f(x)$ also satisfies the property, and vice versa. So let $f(1) \ge 0$ (otherwise flip all the signs). $|f(1)-f(0)| = 1$, so $f(1) = 1$. Now we induct that $f(x) = x$ for all $x \ge 0$. For $x=0,1$, this is true. Suppose for $x=k-2,k-1$ this is true, then: $|f(k) - f(k-1)| = 1$ $f(k) = f(k-1)+1 \vee f(k-1)-1$ $f(k) = k \vee k-2$ But $f(k-2) = k-2$. Because $f$ is a bijection, we have $f(k) = k$. So the claim is proven. Similarly, we induct that $f(x) = x$ for all $x \le 1$. For $x=1,0$, this is true. Suppose for $x=k+2,k+1$ this is true, then: $|f(k) - f(k+1)| = 1$ $f(k) = f(k+1) + 1 \vee f(k+1) - 1$ $f(k) = k+2 vee k$ But $f(k+2) = k+2$. Because $f$ is a bijection, we have $f(k) = k$. So the claim is proven. Now the conclusion is obvious: $|f(i)-f(j)| = |i-j| \le |i-j|$.

the given condition implies that $f(i),f(i+1),....,f(i+k)$ are $k+1$ consecutive integers if not all $f(i)$ are in order then there exist $i$ such that $f(i-1),f(i),f(i+1)$ such that f(i) is either biggest or smallest. WLOG it's the biggest and WLOG $f(i+1)$ is the middle one. than $f(i-k),f(i-k+1),....,f(i)$ can't be $k+1$ consecutive integers which is a contradiction.

Whee misread problem. Thought that we can substitute $k$ for any number less than or equal to a given $k$ (which is also a name conflict). Anyway. Let "For all integers $i$ and $j$ such that $|i-j| \le k$, we have $|f(i)-f(j)| \le k$" be called the condition. This can be restated as "For all integers $i$ and $j$ such that $|i-j| \le k$, we have $f(j)-k \le f(i) \le f(j)+k$". Note that $f(i-k), f(i-k+1), f(i-k+2), \ldots, f(i+k)$ are $2k+1$ distinct integers due to the bijectivity. Also, if we let $f(i) = a$, we have $a-k \le f(j) \le a+k$ for all $j=i-k, i-k+1, i-k+2, \ldots, i+k$ due to the condition. There are $2k+1$ integers in $[a-k,a+k]$, so we have $\{f(i-k), f(i-k+1), f(i-k+2), \ldots, f(i+k)\} = \{a-k, a-k+1, a-k+2, \ldots, a+k\}$. Similarly, $\{f(i+1-k), f(i+1-k+1), \ldots, f(i+1+k)\} = \{b-k, b-k+1, b-k+2, \ldots, b+k\}$ where $b = f(i+1)$. Now, note that their intersection is a set of $2k-2$ elements (namely $\{f(i-k+1), f(i-k+2), \ldots, f(i+k)\}$). Hence $b = a-1 \vee a+1$ (otherwise the intersection is less than $2k-2$ elements). This gives $f(i+1) = f(i) + 1$ or $f(i+1) = f(i) - 1$ for all $i$. Then proceed with my earlier proof.

İt's easy to prove that: $\forall n\in \mathbb{Z} ~and ~n\geq 0 \\ |f(x+2^n)-f(x)|=2^n$ So we have $|f(x+2^n)-f(x+2^n-1)|=1~and~ |f(x+2^n)-f(x)|=2^n$. Clearly we obtain $|f(x+2^n-1)-f(x)|=2^n-1$ and similarly $\forall m\in\mathbb{N} ~and~m\leq2^n \\|f(x+2^n-m)-f(x)|=2^n-m$ And we're done.