Suppose one has a recurrence relation, for example:

$$c_{n+2} = c_{n+1} + c_n$$ which is the Fibonacci sequence ($c_0 = 0, c_1 = 1$ ), and the task is to find an explicit formula for $c_n$ using generating functions.

Then one defines $$f(z) = \sum_{z = 0}^{\infty}c_n z^n$$ multiply both sides of the relation, and solve for $f(z)$, giving: $$f(z) = \frac{-z}{z^2 + z -1}$$ Where I'm having trouble is the following: Since $f(z)$ is defined by the power series given above, $c_n = \frac{1}{n!}\frac{d^nf}{dz^n}|_{z=0}$. But alternately, my lecturer said that it can be given by: $$c_n = \frac{1}{2\pi i}\oint \frac{dz}{z^{n+1}}f(z)$$ which can then be evaluated easily with the Residue Theorem, and so on.

However, why is this so (i.e. why is $c_n = \frac{1}{2\pi i}\oint \frac{dz}{z^{n+1}}f(z)$)? In other words, how does this extract the $c_n$ from the series?

  • $\begingroup$ $c_n = \frac{1}{2\pi i}\oint \frac{dz}{z^{n+1}}f(z)$ is en.wikipedia.org/wiki/Cauchy%27s_integral_formula – You tagged the question with [cauchy-integral-formula], so apparently you know about it. Are you asking why this formula holds, or how it can be applied here? $\endgroup$ – Martin R Feb 22 '18 at 7:56
  • $\begingroup$ How it can be applied here, but I don't fully understand why it holds, either. Any help on either count would be greatly appreciated. $\endgroup$ – Shreyas B. Feb 22 '18 at 8:00

Both your formulas for $c_n$ are correct, but they are of not much help in obtaining the $c_n$ numerically. Instead find the roots of the denominator of $f(z)$ and decompose $f(z)$ into partial fractions. These can then be expanded into geometric series in terms of powers of $z$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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