On Some Non-Holonomic Sequences

Abstract

A sequence of complex numbers is holonomic if it satisfies a linear recurrence with polynomial coefficients. A power series is holonomic if it satisfies a linear differential equation with polynomial coefficients, which is equivalent to its coefficient sequence being holonomic. It is well known that all algebraic power series are holonomic. We show that the analogous statement for sequences is false by proving that the sequence $\{\sqrt{n}\}_n$ is not holonomic. In addition, we show that $\{n^n\}_n$, the Lambert $W$ function and $\{\log{n}\}_n$ are not holonomic, where in the case of $\{\log{n}\}_n$ we have to rely on an open conjecture from transcendental number theory.