How to apply the Transfer Theorem on $\frac{z}{1-z-z^2}$ and $\frac{1+z-\sqrt{z^2-6z+1}}{4}$?

59 Views Asked by At

I am tasked to use the Transfer Theorem (see pictures below) to find asymptotic estimations of the coefficients of the OGFs described by $$A(z) := \frac{z}{1-z-z^2}$$ and $$B(z) := \frac{1+z-\sqrt{z^2-6z+1}}{4}.$$ Remark: The pictures are taken from the slides accompanying the Flajolet & Sedgewick book.

I recognise that $A(z)$ describes the OGF of the Fibonacci numbers and thus the radius of convergence is $\phi^{-1} = \frac{\sqrt{5}-1}{2}$.

Concerning $B(z)$ we see that the radius of convergence is $3-\sqrt{8}$.

However, I do not see how to apply the Transfer Theorem in these cases, as they are not in the required form $\frac{f(z)}{(1-z)^\alpha}$ or similar. Could you please help me?

enter image description here

enter image description here