We focus on the set $S = \{1, f(1), f^2(1), \dots\}$. Observe that $S$ is unbounded, because for every $n$ in $S$, there exists $k > 0$ such that $f^{2k}(n) = n + k$ lies in $S$. Clearly $f$ maps $S$ into itself, and $f$ is one-to-one on $S$. Indeed, if $f^i(1) = f^j(1)$ (with $i$ and $j$ unequal), then starting from some $m$, $f^m(1)$ would recur periodically, and $S$ would be finite.

Define $g : S \to S$ by $g(n) = f^{2k_n}(n) = n + k_n$. We show that $g$ is also one-to-one.

Suppose $g(a) = g(b)$ with $a < b$. Then $a + k_a = f^{2k_a}(a) = f^{2k_b}(b) = b + k_b$, from which we get $k_a > k_b$. So, since $f$ is one-to-one on $S$, we obtain $f^{2(k_a - k_b)}(a) = b = a + (k_a - k_b)$. However, since $0 < k_a - k_b < k_a$, this contradicts the minimality of $k_a$.

Let $T$ be the set of elements of $S$ excluding those of the form $g(n), n \in S$. Note that $1 \in T$ since $g(n) > n$ for $n \in S$, so $T$ is not empty. For each $t \in T$, let $C_t = \{t, g(t), g^2(t), \dots\}$; this $C_t$ is called the chain starting at $t$. We observe that distinct chains are mutually exclusive, since $g$ is one-to-one. Every $n \in S \setminus T$ can be expressed as $n = g(n')$, where $n' < n, n' \in S$. By the same reasoning, we observe that for some $t \in T, n \in C_t$, that is, $S$ is the union of these mutually exclusive chains $C_t$.

If $f^n(1)$ lies in $C_t$ starting at $t = f^{n_t}(1)$, then $n = n_t + 2a_1 + \cdots + 2a_j$ and $f^n(1) = g^j(f^{n_t}(1)) = f^{2a_j}(f^{2a_{j-1}}(\cdots f^{2a_1}(f^{n_t}(1)))) = f^{n_t}(1) + a_1 + \cdots + a_j$.

Therefore
$$f^n(1) = f^{n_t}(1) + \frac{n - n_t}{2} = t + \frac{n - n_t}{2}. \quad (1)$$

Now we use proof by contradiction to show that $T$ is infinite. Suppose there are only finitely many chains $C_{t_1}, \dots, C_{t_r}$, starting at $t_1 < \dots < t_r$. Fix $N$. If $f^n(1), 1 \le n \le N$ lies in $C_t$, then

by equation (1), $f^n(1) = t + \frac{n-n_t}{2} \le t_r + \frac{N}{2}$. But the $N+1$ distinct numbers $1, f(1), \cdots, f^N(1)$ are all less than $t_r + \frac{N}{2}$, so $N+1 \le t_r + \frac{N}{2}$. So when $N$ is sufficiently large we get a contradiction, hence $T$ is infinite.

Choose any $k \in \mathbb{N}$ and consider the $k+1$ chains headed by the first $k+1$ numbers in $T$. Let $t$ be the largest of these numbers. Each chain contains a number not exceeding $t$, and at least one chain does not contain any of $t+1, \cdots, t+k$. So in this chain there exists a number $n$ such that $g(n)-n > k$, that is, $k_n > k$. Hence $k_1, k_2, \cdots$ is unbounded.