Hypergeometric solutions of linear recurrences with polynomial coefficients (Q1199820)

Let \(a(n)\) be a sequence over a field \(K\) of characteristic zero. We say that \(a(n)\) is hypergeometric if there is a rational function \(r(x) \in K(x)\) such that \(a(n+1) = r(n) a(n)\) for all sufficiently large integers \(n\). Given any linear recurrence with polynomial coefficients in \(K_ 0(n)\) and an extension field \(K\) of \(K_ 0\), the author presents an algorithm that will determine whether or not this recurrence has a hypergeometric solution over \(K\). He also describes an extension of the algorithm that will determine if there is a solution in the linear space spanned by the hypergeometric sequences. The algorithms explicitly construct solutions when they exist and, in the case of a homogeneous linear recurrence, a basis for the solution set.