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.

integers. $\endgroup$ – Aaron Meyerowitz May 21 '17 at 19:05