Polynomially recursive sequences (Q2716528)

Let \(S\) be the algebra of sequences \(f=(f_n)_{n\geq 0}\) with terms \(f_n\) in the field \(k\). Let \(D\) be the shift operator given by \((Df)_n=f_{n+1}\). A sequence \(f\) in \(S\) is polynomially recursive if there are polynomials \(p_0(x), \ldots, p_r(x)\) such that \((p_0(x)D^r-p_1(x)D^{r-1}-\cdots-p_r(x)I)(f)=0\), that is \(p_0(n)f_n=p_1(n-1)f_{n-1}+\cdots+p_r(n-r)f_{n-r}\) for \(n\geq r\). The sequence is called hypergeometric if it satisfies such a relation of degree 1 in \(D\). The well-known linearly recursive sequences arise if the coefficients \(p_i(x)\) are constant. The author describes a number of algebraic constructions on these spaces which extend classical formulae for linear recrusive sequences. Finally, there is an interesting extension to \(q\)-polynomially recursive sequences satisfying \(p_0(q^n)f_n=p_1(q^{n-1})f_{n-1}+\cdots+p_r(q^{n-r})f_{n-r}\).