, 2012

The answer is all $k \neq 2$. If $k = 2$, note that $f(f(n)) = 2n$ implies that $f(n) \neq n$ for all $n$. Therefore $f(1) \neq 1$. We also have $f(1) \neq 2$ since then $f(f(1)) = f(2) = 2$, so $f(1) > 2$. But then $2 = f(f(1)) < f(1)$ while $f(1) > 1$, so we have a contradiction of the second condition.

For $k = 1$, we simply take $f(n) = n$. We give an algorithm to construct a function that works for any $k > 2$. Note that each time we set $f(a) = b$, this implicitly means we also set $f(k^m a) = k^m b$ and $f(k^m b) = k^{m+1} a$. Begin by setting $f(1) = 2$. Then repeat the following: for the smallest number $m$ for which $f(m)$ has yet to be defined, set $f(m) = m'$ where $m'$ is the smallest nonmultiple of $k$ greater than $f(m-1)$. It is clear we will obtain $f(f(n)) = kn$ this way for all $n$; we now need to show $f(n) < f(n+1)$. We go by strong induction, with $n = 1$ obvious. Given it is true up to $n$, we show $f(n) < f(n+1)$ with two cases:

(i) $f(n+1)$ is not a multiple of $k$: This means $n+1$ was selected as an $m$ in the algorithm, and $f(n+1)$ was deliberately set to be greater than $f(n)$.

(ii) $f(n + 1)$ is a multiple of $k$: Let $x$ be the largest integer less than or equal to $n$ such that $f(x)$ is a multiple of $k$. Because all multiples of $k$ map to multiples of $k$ under $f$, we have $n - k < x \le n$. Let $f(x) = ka$ and $f(n+1) = kb$. Then $f(a) = x$ and $f(b) = n + 1$. Since $x < n + 1$ and $a, b < n$, the inductive hypothesis implies $a < b$. Note that for each $m \in \{n - x + 1, n - x + 2, \dots, n\}$, $f(m)$ was set equal to $f(m - 1) + 1$. So this means that the algorithm would have set $f(n) = f(x) + (n - x) = ka + (n - x)$. Since $n - x < k$, $ka + (n - x) < k(a + 1) \le kb$. Therefore $f(n) < f(n + 1)$ as desired.