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.