co.combinatorics - Recursions which define polynomials

I have no answer to your question, but some related examples.
Consider the q-Fibonacci polynomials defined by f(0, x, s)=0, f(1, x, s)=1 and f(n, x, s)=x f(n-1, x, s)+q^(n-2) s f(n-2, x, s).
Then the subsequences f(k n, x, s) satisfy a homogeneous recursion with rational coefficients which for k>2 are not polynomials (see e.g. my paper in arXiv 0806.0805).

More precisely
f(k, x, q^k s) f(k n, x, s) – f(2 k, x, s) f(k (n-1), x, q^k s)
+(-1)^k q^(k(3k-1)/2) s^k f(k, x, s) f(k (n-2), x, q^(2k) s)= 0
or equivalently

f(k, x, q^(n-2k) s) f(k n, x, s) – f(2 k, x, q^(k (n-2)) s) f(k (n-1), x, s)
+(-1)^k q^(-k (3k+1)/2) q^(k^2 n) s^k f(k, x, q^(k (n-1)) s) f(k (n-2), x, s)= 0.

Analogous results are true for powers of q-Fibonacci polynomials.