Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
Think in terms of partial fractions and geometric series expansions. –  anon Jul 17 '12 at 17:01
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)$? –  Robert Israel Jul 17 '12 at 17:55
    
Got something from an answer below? –  Did Jul 25 '12 at 16:32
add comment

2 Answers

  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$.
share|improve this answer
    
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
1  
@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
add comment

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:

https://docs.google.com/file/d/0B4FXAHVyGS9KMGRiNDMyNDctMmQ1NS00MDI3LTk2OWEtNzc3N2ZlNDVmYjJm/edit?hl=en_GB&pli=1

share|improve this answer
1  
Once you have the partial fraction decomposition (as in your thesis), you hardly need explicit formulas for the derivatives; the standard geometric-series classification (as in anon's comment) is a much easier way of seeing the same thing. –  Steven Stadnicki Jul 17 '12 at 19:44
    
My point was to give him an idea to prove his assertion by exploiting the nth derivative of his rational polynomial. –  Mhenni Benghorbal Jul 17 '12 at 20:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.