  We investigate the decidability of the monadic second-order (MSO) theory of
the structure $\langle \mathbb{N};<,P_1, \ldots,P_k \rangle$, for various unary
predicates $P_1,\ldots,P_k \subseteq \mathbb{N}$. We focus in particular on
"arithmetic" predicates arising in the study of linear recurrence sequences,
such as fixed-base powers $\mathsf{Pow}_k = \{k^n : n \in \mathbb{N}\}$, $k$-th
powers $\mathsf{N}_k = \{n^k : n \in \mathbb{N}\}$, and the set of terms of the
Fibonacci sequence $\mathsf{Fib} = \{0,1,2,3,5,8,13,\ldots\}$ (and similarly
for other linear recurrence sequences having a single, non-repeated, dominant
characteristic root). We obtain several new unconditional and conditional
decidability results, a select sample of which are the following:
  $\bullet$ The MSO theory of $\langle \mathbb{N};<,\mathsf{Pow}_2,
\mathsf{Fib} \rangle$ is decidable;
  $\bullet$ The MSO theory of $\langle \mathbb{N};<, \mathsf{Pow}_2,
\mathsf{Pow}_3, \mathsf{Pow}_6 \rangle$ is decidable;
  $\bullet$ The MSO theory of $\langle \mathbb{N};<, \mathsf{Pow}_2,
\mathsf{Pow}_3, \mathsf{Pow}_5 \rangle$ is decidable assuming Schanuel's
conjecture;
  $\bullet$ The MSO theory of $\langle \mathbb{N};<, \mathsf{Pow}_4,
\mathsf{N}_2 \rangle$ is decidable;
  $\bullet$ The MSO theory of $\langle \mathbb{N};<, \mathsf{Pow}_2,
\mathsf{N}_2 \rangle$ is Turing-equivalent to the MSO theory of $\langle
\mathbb{N};<,S \rangle$, where $S$ is the predicate corresponding to the binary
expansion of $\sqrt{2}$. (As the binary expansion of $\sqrt{2}$ is widely
believed to be normal, the corresponding MSO theory is in turn expected to be
decidable.)
  These results are obtained by exploiting and combining techniques from
dynamical systems, number theory, and automata theory.
