Assume that the sequence $\{a_n\}$ is unbounded. Let $x$ be the smallest prime such that $x \nmid k$. Take a huge $N$ and choose $m$ such that $a_m$ is the first integer greater than or equal to $N$. Then by definition, $a_m \geq N , a_{m-1} < N$. So this implies that $a_{m-1}$ is prime, since otherwise $a_m = a_{m-1} - f(a_{m-1}) < a_{m-1} < N$. So $a_{m-1} + k = a_m \geq N \implies a_{m-1} \geq N - k$. If $a_{m-2}$ is not prime, then $a_{m-2} - f(a_{m-2}) = a_{m-1} \implies a_{m-2} = 2a_{m-1} > N$, contradiction with our assumption. Thus $a_{m-2}$ is prime. If $a_{m-3}$ is not prime, $a_{m-3} = 2a_{m-2} > N$, contradiction with our assumption. Because of our choice of huge $N$, we can obtain in a similar fashion that $a_{m-1} , a_{m-2} , \dots , a_{m-x}$ are all primes. So, the sequence $a_m , a_{m-1} , \dots , a_{m-x}$ is an arithmetic progression with common difference $k$. Let $a_m = T$. Then, $a_{m-i} = T - ik$ is prime for all $1 \leq i \leq x$. But note that $a_{m-i} \equiv a_{m-j} \pmod{x} \iff (i-j)k \equiv 0 \pmod{x} \iff i \equiv j \pmod{x} \iff i = j$. So, $\{a_{m-1} , a_{m-2} , \dots , a_{m-x}\}$ forms a complete residue system modulo $x$, in particular there exists $j$ such that $a_j \equiv 0 \pmod{x}$, and because $T$ is large, $a_j \neq x$, implying that $a_j$ is not prime, contradiction. Thus our assumption was wrong and the sequence is bounded.