By trivial induction, $x_{k}$ is coprime to $d$. By induction and the fact that there can be at most $a-1$ consecutive increasing terms in the sequence, it also holds that $x_{k}<d a$ if $x_{k}=x_{k-1}+d$ and that $x_{k}<d$ if $x_{k}=\frac{x_{k-1}}{a}$ or $k=1$. This gives the upper bound on the exponent. This implies that the sequence is (eventually) periodic, and that both increasing and decreasing steps happen infinitely many times. Let $a^{-k}$ be the multiplicative inverse of $a^{k}$ modulo $d$. The sequence contains elements congruent to $1, a^{-1}, a^{-2}, \ldots$ modulo $d$. Let $x_{k_{0}}$ the first element such that $x_{k_{0}} \equiv a^{-n}(\bmod d)$. We have either $k_{0}=1$ or $x_{k_{0}}=$ $x_{k_{0}-1} / a$; in both cases $x_{k_{0}}<d<a^{n}<d a$ and therefore
$$x_{k_{0}} \in\left\{a^{n}-d, a^{n}-2 d, \ldots, a^{n}-(a-1) d\right\}$$
In this set no element is divisible by $a$, so therefore the sequence will visit the value $a^{n}$ in the next $a-1$ steps.