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](https://en.wikipedia.org/wiki/Constant-recursive_sequence); 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.



Possible behaviors of integer sequences that arise from powering nonnegative integer matrices
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](http://people.brandeis.edu/~gessel/homepage/slides/nonneg.pdf) 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](https://arxiv.org/abs/math/0506398)): 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](http://www.sciencedirect.com/science/article/pii/0304397576900840), 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}$.


