Generating function of a sequence is not algebraic

Question

Let we have a sequence $\{a_{n}\}$, such that $\forall n \,\, a_{n}>0$ and $a_{n} \rightarrow\infty, n\rightarrow\infty$. Also let's suppose that we have a subsequence $\{a_{n_{k}}\}$ such that $\exists C>0$ $\forall k:$ $a_{n_{k}}<Clog\, n_{k} $. How can we prove that the generating function of $\{a_{n}\}$ can't be an algebraic function?

Answer 1

Yes, we can. Asymtotics of the coefficients of an algebraic function is determined by the finitely many singularities on the circle of convergence. At every singularity the algebraic function has a Puiseux exansion, from which follows that the function has a power asymptotics (no logs). This paper is a convenient reference for the relation between the asymptotics of the function and asymptotics of its power series:

MR1039294
Flajolet, Ph., Odlyzko, A., Singularity analysis of generating functions. SIAM J. Discrete Math. 3 (1990), no. 2, 216–240.

Inspection of all cases shows that no subsequence of coefficients of an algebraic function can have the intermediate growth between the constant and the logarithm. More precisely, constant can happen but log cannot. So your conditions that the coefficients tend to infinity but no faster than the log exclude algebraic functions.