Complexity of powers of a constant-recursive sequence

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 ${(\text{rank}s(n{)}^M)}_{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.