# Solving recurrence relations using generating functions with complex analysis

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?

• $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? – Martin R Feb 22 '18 at 7:56
• 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. – Shreyas B. Feb 22 '18 at 8:00

## 1 Answer

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$.