Complexity of powers of a constant-recursive sequence

Abstract

Constant-recursive sequences are those which satisfy a linear recurrence, so that later terms can be obtained as a linear combination of the previous ones. The rank of a constant-recursive sequence is the minimal number of previous terms required for such a recurrence. For a constant-recursive sequence $s(n)$, we study the sequence ${\left(\text{rank}s(n{)}^M\right)}_{M\ge 1}$. We answer a question of Stinchcombe regarding the complexity of the powers of a constant-recursive sequence when the roots of the characteristic polynomial are not all distinct.

23 pages, 3 tables