Fibonacci( Binet's Formula Derivation)-Revised with work shown

Question

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?

Answer 1

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.

Answer 2

Here is my take on what is trying to be achieved here.

Let $\gamma_r(t)=re^{it}$ for $t\in[0,2\pi]$ and $$ F(z)=\sum_{k=0}^\infty f_kz^k=\frac{z}{1-z-z^2}\tag{1} $$ Define $$ \omega_\pm=\dfrac{-1\pm\sqrt{5}}{2}\tag{2} $$ Then $1-z-z^2=(w_\mp-z)(z-w_\pm)$.

The residue of $\dfrac{F(z)}{z^{n+1}}=\dfrac1{z^n(1-z-z^2)}$ at $0$ (the coefficient of $1/z$) is $f_n$.

The residue of $\dfrac{F(z)}{z^{n+1}}$ at $\omega_\pm$ is $\dfrac1{\omega_\pm^n(\omega_\mp-\omega_\pm)}$; i.e. multiply by $(z-\omega_\pm)$ and evaluate at $\omega_\pm$.

As $r\to\infty$, $|F(z)|\sim\frac1r$ on $\gamma_r$. Therefore, for $n\ge0$, $$ \lim_{r\to\infty}\int_\gamma\frac{F(z)}{z^{n+1}}\,\mathrm{d}z=0\tag{3} $$ Thus, by the Residue Theorem, the sum of the residues at $0$, $\omega_+$, and $\omega_-$ must be $0$, that is $$ \begin{align} 0 &=f_n+\frac1{\omega_+^n(\omega_--\omega_+)}+\frac1{\omega_-^n(\omega_+-\omega_-)}\\ &=f_n-\frac{\phi^n}{\sqrt5}+\frac{(-1/\phi)^n}{\sqrt5}\tag{4} \end{align} $$ where we note that $\omega_+=1/\phi$ and $\omega_-=-\phi$ ($\phi$ is the Golden Ratio). $(4)$ implies Binet's Formula: $$ f_n=\frac{\phi^n-(-1/\phi)^n}{\sqrt5}\tag{5} $$

Answer 3

Let $$F(x) = \frac{1}{1-x-x^2} = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + 21x^7 + 34x^8 + \ldots$$

Put $\varphi = \frac{\sqrt{5}+1}{2}$ and $\bar \varphi$ its conjugate, these are the two roots of $1-x-x^2$.

(1) Then $F(x)$ has a positive radius of convergence by the ratio test which gives $r = \lim_{n \to \infty} |f_n/f_{n+1}| = \bar \varphi$.

(2) $1 = (1-x-x^2)F(x) = F(x) - x F(x) - x^2 F(x)$ so the coefficients of this generating function satisfy the same recurrence as the fibonacci sequence. In fact $x^n$ is $f_n$ the $n$th fibonacci number.

(3) $\text{Res}(\frac{1}{z^{n+1}(1-z-z^2)},z=0) = f_n$ by the residue limit formula for higher poles.

(4) By Theorem 9.9 which states $$\int_{\gamma} f(z) dz = 2 \pi i \sum_{\rho} \text{Res}(f(z)),z=\rho)$$ summing over all residues we have $$\int_{\gamma} \frac{dz}{z^{n+1}(1-z-z^2)} = 2 \pi i [f_n + R_\varphi + R_{\bar \varphi}]$$ since there are three residues (one at 0, one at $\varphi$, one at $\bar \varphi$.)

For the integral let $\gamma(t) = R e^{it}$ so we have $$\int_0^{2 \pi} \frac{i R e^{it} dt}{R^{n+1}e^{it(n+1)}(1-(Re^{it})-(Re^{it})^2)}$$ and as $R \to \infty$ this integral tends vanishes since the denominator becomes infinite: look at each factor, $R^{n+1}$ obviously blows up, $e^{it(n+1)}$ has absolute value 1 so it's ignorable, for $R > \varphi$ the last factor $(1-(Re^{it})-(Re^{it})^2)$ will always be bounded below by some constant, so we can ignore this too.

For the other two residues we can use the residue formula for simple poles: $$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)} = \frac{1}{\varphi^{n+1}(1-\bar \varphi)}$$

Answer 4

The theorem gives us $$\int_{\gamma} \frac{dz}{z^{n+1}(1-z-z^2)} = 2 \pi i [f_n + R\varphi + R_{\bar \varphi}]$$

and we prove that the integral tends to 0 as R tends to infinity, so that gives us

$$0 = 2 \pi i [f_n + R\varphi + R_{\bar \varphi}]$$

(as the RHS didn't depend on R) thus

$$f_n = -R\varphi - R_{\bar \varphi}$$

and these Residue terms should simplify into Binets formula once they are calculated correctly.