Holonomic sequence

Remarks

Example: the factorials $u_n = n!$ form a holonomic sequence over $\Q$, with $r = 1$, $p_1 = 1$ and $p_0 = -(n + 1)$, since $(n+1)! - (n+1) \cdot n! = 0$. Non-example: $u_n = 2^{n^2}$ over $\Q$ is not holonomic. Indeed, take a recurrence as above with $p_r \ne 0$ and the other $p_i$ of degree at most $f$. It gives $\abs{u_{n+r}} \le C n^{f} \max_{i < r} \abs{u_{n+i}}$ for large $n$ and some constant $C$. So $\log \abs{u_n}$ grows at most like a constant times $n \log n$, while $\log 2^{n^2} = n^2 \log 2$. Over a field of characteristic $0$, $u$ is holonomic if and only if its generating function $\sum u_n x^n$ is a holonomic function. Every solution of a linear recurrence with constant coefficients is holonomic.