Possible behaviors of integer sequences that arise from powering nonnegative integer matrices Let's call a sequence of nonnegative integers $x_1,x_2,\ldots$ matrix-realizable, if there exists a $k\times k$ nonnegative integer matrix $A$ (for some $k$), as well as nonnegative integer vectors $u,v$, such that
$x_n = u^T A^n v$
for all $n$.  (So in particular, all matrix-realizable sequences are linearly recurrent sequences; because of the nonnegative integer constraints, I don't know whether the converse holds.)
I'm interested in the possible patterns of decreases in matrix-realizable sequences.  For example:


*

*Is there any matrix-realizable sequence $(x_n)$ such that $x_{2n} > x_{3n+1}$ for all $n$?


*Is there any matrix-realizable sequence $(x_n)$ such that $x_n > x_{n+1}$ whenever $n$ is composite?


In case you care about the motivation: these questions arose from a project I've been working on with Marijn Heule and Luke Schaeffer about computer-generated proofs.  If the answers to the questions are "no," then it follows that there can be no computer-generated proofs of a very particular format (which we call "unary matrix proofs") for various interesting statements.  In the above two examples, those statements are the Collatz Conjecture and the infinitude of primes, respectively.
 A: Such sequences are linear combinations of (complex) exponentials times polynomials $p(n)e^{\lambda n}$ (bring $A$ to Jordan normal form to see this, or use the fact you mentioned). So for large $n$, they look like
$$
x_n= n^k e^{an} \sum c_j \cos (\omega_j n -\alpha_j) +o(n^ke^{an}) .
$$
The quasi-periodic sequence $\sum c_j \cos(\ldots)$ is obtained by evaluating a continuous function on a torus along the orbit of a translation in that group, so if observed long enough, it will come close to all points in the closure of its range and return over and over again. Since there are arbitrarily long gaps in the primes, this is clearly incompatible with your second scenario.
A: The answer is "no" for both questions. 
The rational functions $a_0+a_1x+a_2x^2+\cdots$ with non-negative integer entries which can be obtained by $a_n=u^{T}A^nv$ for some nonnegative vectors $u,v$ and matrix $A$ are called $\mathbb N$-rational in the literature. Here are some slides by I. Gessel that provide a quick introduction. For a deeper treatment there is the book "Noncommutative Rational Series with Applications" by Jean Berstel and Christophe Reutenauer, especially the first 8 chapters (the rest of the book deals with noncommutative generalizations).
First, as it was mentioned by others, not only is there no $\mathbb N$ rational series satisfying the second bullet point, there is in fact no such linear recurrence relation. If we take the power series
$$h(t)=(t-1)(x_0+x_1t+x_2t^2+\cdots)$$
we get a rational function with positive coefficients at every composite integer. The condition that the $x_i$ are nonnegative implies that $h$ must have infinitely many negative coefficients at a sparse set. However a theorem of Bell and Gerhold says that this is impossible (reference): the set of indices where the coefficients are negative must have positive density! 
For the first bullet point I'm not sure what happens for general linear sequences, but we can restrict to $\mathbb N$-rational since these are a bit more special, and are the ones relevant to your question. A theorem of Berstel (see page 318 here, or chapter 8 of the book above), says that for such sequences there exist some $m,p\in \mathbb N$ for which the subsequences $\{x_{m+pk+i}\}_{k=1}^{\infty}$, for $i\in\{0,2,\dots,p-1\}$ are all of the form $P_i(k)\alpha_i^k +o(P_i(k)\alpha_i^k)$. Therefore each such subsequence has terms that are constant or strictly increasing. However if we take $n=qp-1$ for large enough $q$ we have $(3n+1)-(2n)=qp$, so $x_{2n},x_{3n+1}$ are in the same subsequence and therefore we can't have $x_{2n}>x_{3n+1}$.
