4
$\begingroup$

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?

  • 6
    Think in terms of partial fractions and geometric series expansions.2012-07-17
  • 1
    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)$?2012-07-17
  • 0
    Got something from an answer below?2012-07-25

2 Answers 2