Okay so here is the revised question with my current work.
Links to previous post(s)(Just for Gerry): Fibonacci Numbers – Complex Analysis
Here's my attempt on the problem set thus far: (Note that $\bullet$ represents a completed problem (in my opinion) while $\circ$ represents a semi-completed problem.)
~Problem set can be found on page 106: http://www.math.binghamton.edu/sabalka/teaching/09Spring375/Chapter10.pdf
(2) To derive a generating function for $f_n$, note that the fibonacci series is defined by the sequence of numbers $(0,1,f_1+f_0,f_2+f_1,…f_n+f_n-1)$.
If we break this up into three separate generating functions and sum them to obtain the generating function $F(z)$ it will look something like:
$$(0,1,0,0,0…) \rightarrow\,z)$$
$$+(0,f_0,f_1,f_2,…)\to\,zF(z)$$ for a $F(z) = f_0+f_1z+f_2z^2+…+f_nz^n$
$$+ (0,0,,f_0,f_1,f_2,…)\to z^2F(z)$$ for the same $F(z)$
This all equals $$(0,1+f_0,f_1+f_0,f_2+f_1,f_3+f_2,…)\to z+zF(z)+z^2F(z)$$
Therefore $F(z)=z+zF(z)+z^2F(z)$, solving for $F(z)$ we obtain
$$F(z) = \frac {z}{1-z-z^2} \bullet$$
P.S. I don't understand why it says $\frac{1}{1-z-z^2}$ instead of $\frac{z}{1-z-z^2}$ in the original problem set. Is it because they're excluding the $f_0$ and $f_1$ terms?
~
I felt that it would make more sense to do (2) before (1) so here's (1)
*First note that by the quadratic formula, the two roots of the denominator are $\varphi,\bar \varphi$ where $\varphi= \frac {1+\sqrt5}{2}$.
So $F(z)$ has a positive radius of convergence by the ratio test which gives
$r=\lim_{n\to\infty}\frac{f_n+1}{f_n}= \bar \varphi \bullet$
~
(3) Now to show that $Res (\frac{1}{z^n+1(1-z-z^2)})$ at $z=0$ = $f_n$
I know that you must use the formula:
$Res(f,c) = \frac{1}{n-1!}\lim_{z\to c}\frac{d^n-1}{dz^n-1} ((z-c)^nF(z)$ for a pole of order n. I need a little help here. I'm also confused as to where they get the $z^n+1$ from. Why does it appear there? $\circ$
Edit
I realized that since
$$1=Res_{z=0}z^{-1}$$ then z^n+1 would be the extracting term:
$$f_n=Res_{z=0}\frac{1}{z^{n+1}} \sum_{n>1}{f_nz^n}$$
Is this correct?
Edit According to Brian M. Scott, the proper work for this problem (3) is
$$\begin{align*}
\operatorname{Res}_{z=0}\left(\frac1{z^{n+1}(1-z-z^2)}\right)&=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\left(z^{n+1}\frac1{z^{n+1}(1-z-z^2)}\right)\\
&=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\big(F(z)\big)\\
&=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\sum_{k\ge 0}f_kz^k\\
&=\frac1{n!}\lim_{z\to 0}\sum_{k\ge 0}f_k\frac{d^n}{dz^n}z^k\\
&=\frac1{n!}\lim_{z\to 0}\sum_{k\ge n}f_k \Big( \prod_{i=0}^{n-1} (k-i) \Big)z^{k-n}\\
&=\frac1{n!}\lim_{z\to 0}\left(f_nn!+\sum_{k>n}f_k \Big( \prod_{i=0}^{n-1} (k-i) \Big) z^{k-n}\right)\\
&=f_n+\frac1{n!}\lim_{z\to 0}z\sum_{k\ge n+1}f_k \Big( \prod_{i=0}^{n-1} (k-i) \Big) z^{k-(n+1)}\\
&=f_n\; \bullet
\end{align*}$$
I follow this work until the third to last step where I don't understand how he obtained the $f_nn!$ term. Any Explanations?
(4)
Using the residue theorem $$\int_{\gamma} f(z) dz = 2 \pi i \sum_{\rho} \text{Res}(f(z)),z=\rho)$$
Now quite obviously applying this:
$$\int_{\gamma} \frac{dz}{z^{n+1}(1-z-z^2)} = 2 \pi i [f_n + R\varphi + R_{\bar \varphi}]$$
Okay, so obviously we must parametrize over a circle of radius R. This parametrization is $\gamma(t) = Re^{it}$ because a circle is just a simple curve.
Performing a change of variables, we obtain $$\int_0^{2 \pi} \frac{i R e^{it} dt}{R^{n+1}e^{it(n+1)}(1-(Re^{it})-(Re^{it})^2)}$$
The only reason that I personally thought of why this integral $\to 0$ is because the one can trivially see that the denominator would be $>>$ than the numerator because you have $\infty$ raised to a power.
I'm also confused as to why it's even necessary to show that this integral disappears as the Radius of the circle approaches $\infty$. Could someone care to explain?
Finally, for the exact calculations of $(R\varphi, R_{\bar \varphi})$
First note that $(1-z-z^2)=(\varphi + z)(\bar \varphi-z)
$$R_\varphi = \text{Res}(\frac{1}{z^{n+1}(1-z-z^2)},z=\varphi) = \lim_{z \to \varphi}\frac{z-\varphi}{z^{n+1}(1-z-z^2)} = \lim_{z \to -\varphi}\frac{z-\varphi}{z^{n+1}(\varphi + z)(\bar \varphi-z)} =\frac{1}{\varphi^{n+1}(1-\bar \varphi)}$$
Alternatively,
$$R_\bar \varphi = \text{Res}(\frac{1}{z^{n+1}(1-z-z^2)},z=\bar \varphi) = \lim_{z \to \bar \varphi}\frac{z-\bar \varphi}{z^{n+1}(1-z-z^2)} = \lim_{z \to \bar \varphi}\frac{z-\bar \varphi}{z^{n+1}(\varphi + z)(\bar \varphi-z)} =\frac{1}{\bar \varphi^{n+1}(1- \varphi)} \circ$
(5) Requires the completion of (4)
This is all of my current work that I have thus far. I honestly do not know where to go from my last step in (4). I still need to arrive at a final identity for $f_n$. So I need to know how to continue this work. Any hints, etc?
Thanks!~
Edit
I now understand that $$f_n=Res (F(z)) at z=0= \Big(Res(F(z) at z=0 + Res(F(z) at z= \varphi + Res(F(z) at z=\bar \varphi\Big) – \Big(Res(F(z) at z= \varphi + Res(F(z) at z=\bar \varphi\Big) = {2\pi i}\int F(z)dz – – \Big(Res(F(z) at z= \varphi + Res(F(z) at z=\bar \varphi\Big) = – \Big(Res(F(z) at z= \varphi + Res(F(z) at z=\bar \varphi\Big) $$ because the integral $$2\pi i\int F(z)dz \to 0$$ as $R \to \infty$
Is this correct?
Best Answer
You got $F(z)=\dfrac{z}{1-z-z^2}$ because you used the standard indexing of the Fibonacci numbers that makes $f_0=0$; your coefficient sequence is $\langle 0,1,1,2,\dots\rangle$. The problem set has $f_0=f_1=1$, so its coefficient sequence is $\langle 1,1,2,3,\dots\rangle$. Yours is right-shifted one place, an operation that corresponds to multiplication by $z$, so your generating function is $z$ times that of the problem. The generating function for the sequence as given in the problem is therefore $\dfrac1zF(z)=\dfrac1{1-z-z^2}$.
The zeroes of $1-z-z^2$ are $\dfrac{-1\pm\sqrt5}2$, or $-\varphi$ and $\dfrac1\varphi$, where as usual $\varphi=\dfrac{1+\sqrt5}2$.
$$\lim_{n\to\infty}\left|\frac{f_{n+1}z^{n+1}}{f_nz^n}\right|=|z|\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\varphi|z|\;,$$
so the radius of convergence is $\dfrac1\varphi=\dfrac{-1+\sqrt5}2$; if this is what you’re calling $\overline\varphi$, your conclusion is correct, but there are some errors along the way to it.
You want to show that $$\operatorname{Res}_{z=0}\left(\frac1{z^{n+1}(1-z-z^2)}\right)=f_n\;.$$ $0$ is a pole of order $n+1$ of the function in parentheses, so you have the formula
$$\begin{align*} \operatorname{Res}_{z=0}\left(\frac1{z^{n+1}(1-z-z^2)}\right)&=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\left(z^{n+1}\frac1{z^{n+1}(1-z-z^2)}\right)\\ &=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\big(F(z)\big)\\ &=\frac1{n!}\lim_{z\to 0}\frac{d^n}{dz^n}\sum_{k\ge 0}f_kz^k\\ &=\frac1{n!}\lim_{z\to 0}\sum_{k\ge 0}f_k\frac{d^n}{dz^n}z^k\\ &=\frac1{n!}\lim_{z\to 0}\sum_{k\ge n}f_kk(k-1)(k-2)\ldots(k-n+1)z^{k-n}\\ &=\frac1{n!}\lim_{z\to 0}\left(f_nn!+\sum_{k>n}f_kk(k-1)(k-2)\ldots(k-n+1)z^{k-n}\right)\\ &=f_n+\frac1{n!}\lim_{z\to 0}z\sum_{k\ge n+1}f_kk(k-1)\ldots(k-n+1)z^{k-(n+1)}\\ &=f_n\;. \end{align*}$$
I’ll leave the rest to someone whose complex analysis doesn’t have some $35$ years of rust on it.