# If a generating function for $f(n)$ is rational, $f(n)$ cannot be more than exponential.

If I have a generating function for $f(n)$ defined by

$g(x)=\displaystyle\sum_{n=0}^{\infty}f(n)x^n=\dfrac{P(x)}{Q(x)}$,

where $P(x)$ and $Q(x)$ are polynomials and $Q(x)$ is not the zero function, how could I show that $f(n)$ is not more than exponential?

-
Think in terms of partial fractions and geometric series expansions. – anon Jul 17 '12 at 17:01
We may assume $Q(0) \ne 0$. The radius of convergence is the least absolute value of a zero of $Q$. What does the root test say about $f(n)$? – Robert Israel Jul 17 '12 at 17:55
Got something from an answer below? – Did Jul 25 '12 at 16:32

1. Since $Q(0)\ne0$, $|Q(z)|\geqslant a$ for every $z$ in a neighborhood of $0$, say for every $|z|\leqslant\varepsilon$, for some $a\gt0$ and $\varepsilon\gt0$.
2. Since $P$ is continuous, $|P(z)|\leqslant b$ for every $|z|\leqslant\varepsilon$, for some finite $b$.
3. For every $n$, $$f(n)=\frac1{2\mathrm i\pi}\oint\frac{P(z)}{Q(z)}\frac{\mathrm dz}{z^{n+1}},$$ where the integral is over the circle of equation $|z|=\varepsilon$, whose length is $2\pi\varepsilon$.
4. In particular, $$|f(n)|\leqslant\frac1{2\pi}2\pi\varepsilon\frac{b}a\frac1{\varepsilon^{n+1}}=cK^n,$$ with $c=b/a$ and $K=1/\varepsilon$.
-
Here we go, you used the idea of the nth derivative of a function. Using the Cauchy's formula for the nth derivative. – Mhenni Benghorbal Jul 17 '12 at 20:22
@Mhenni: Sorry but I fail to see how your comment applies to my answer (which uses no derivative). – Did Jul 18 '12 at 6:50
What you used is the Cauchy formula for the nth derivative of $\frac{P(x)}{Q(x)}$ at the point $x=0$ divide bu $n!$. It is the formula $f(n)=\frac{1}{n!}{\left(\frac{P(0)}{Q(0)}\right)}^{(n)} = \frac{1} {2\pi i} \int_C \frac { P(z) }{ Q(z) }\frac{dz}{z^{n+1}}$. – Mhenni Benghorbal Aug 11 '12 at 22:22

If you look backward to your problem you see that $f(n)$ is nothing, but the nth derivative of your rational polynomial $\frac{P(x)}{Q(x)}$ divided by $n!$. I refer you to my Ph.D thesis (section 6.2.1) which covers the topic of finding the nth derivative of any rational polynomial. In other words you get a closed form formula for the nth derivative which may help you to conclude you assertion: