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

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? - I guess Anthony is going to keep on asking this question in various disguises until someone spoonfeeds the answer. math.stackexchange.com/questions/281109/… and math.stackexchange.com/questions/280378/… --- Anthony, it is extremely unethical to keep posting this problem without linking to your previous questions! – Gerry Myerson Jan 19 '13 at 22:36 Baloney. The record speaks for itself. – Gerry Myerson Jan 19 '13 at 23:12 Anthony, I'll be frank. It's time for you to go and learn the concepts relevant to this question and its solution on your own, say from a textbook about complex analysis. You have been given more than enough advice on what to look for. – Antonio Vargas Jan 19 '13 at 23:14 @GerryMyerson Why do you have to have such a condescendingly pompous tone? I'm just trying to work on this problem set. I've given my personal attempt at the problem set above. Please, stop being such a rude person. – Anthony Peter Jan 20 '13 at 6:51 If you have one question, ask it once. You can amend the question with your work and even post an answer, should you discover one. Posting several questions about the same problem is not appropriate. Your links "Just for Gerry" are not just for Gerry. They should be there, whether Gerry asked for them or not. If you are going to ask several questions regarding the same problem, you should at least link them. – robjohn Jan 20 '13 at 11:24 ## 4 Answers 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. - Thanks so much. Would you mind elaborating a little on the Res(F(z)) atz=0 = f_n? To begin, I don't understand where you pulled the f_nn! from in the third to last step. – Anthony Peter Jan 20 '13 at 17:38 Where does the extra z^{n+1} come from in the first step? – Anthony Peter Jan 20 '13 at 19:09$$\frac1{n!}\lim_{z\to 0}\sum_{k\ge n}f_k \Big( \prod_{0}^{n+1} (k-n) \Big) z^{k-n}\\$$Could you write it like this instead? – Anthony Peter Jan 20 '13 at 19:21 @Anthony: (1) f_nn! is the first term of the sum \sum_{k\ge n}f_kk(k-1)\dots(k-n+1)z^{k-n}, the term when k=n; I just pulled it out of the summation. (2) I want a pole of order n+1 at 0, so I divide F(z), which has no pole at 0, by z^{n+1}. (3) Not quite: \prod_0^{n+1}(k-n) is (k-n)^{n+2}. The correct product is \prod_{i=0}^{n-1}(k-i)). That product is a falling factorial, for which I prefer the notation k^{\underline n}, though (k)_n is also fairly common. – Brian M. Scott Jan 20 '13 at 20:00 @Brain M. Scott. (1) Good, that was my first thought. (2) I understand that, but why do you divide and multiply by z^n+1? I know that the z^n+1 is used to pull out a term f_n, but I'm unclear as to why you put it as a product and a divisor. Is it simply to keep F(z) the same? Did you simply reduce it to 1? (3) Ahh, okay that makes sense. – Anthony Peter Jan 20 '13 at 20:30 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 nth 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)}$$- Thank you so much sir. – Anthony Peter Jan 19 '13 at 22:37 My only question is where the z^n+1 appears from – Anthony Peter Jan 19 '13 at 22:38 For the history of this question/poster, please see my comment on the question. – Gerry Myerson Jan 19 '13 at 22:38 @AnthonyPeter, which z^n+1? also this answer is not complete, I couldn't finish the proof.. that's why I made it community wiki hope someone else will. – user58512 Jan 19 '13 at 22:40 @user58512 Because I'm slowly self-studying complex analysis and this was something that I came across and found interesting. Does that answer your question? – Anthony Peter Jan 19 '13 at 23:48 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} $$- could you elaborate on this part? 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. – Anthony Peter Jan 20 '13 at 21:35 @AnthonyPeter: Other than at z=0, the poles are simple. The residue of f at a simple pole z=c is$$\lim_{z\to c}(z-c)f(z)$$If (z-c)f(z) is continuous, simple evaluation at c suffices. – robjohn Jan 20 '13 at 21:53 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.

-
Isn't that essentially what I put in the edit? –  Anthony Peter Jan 20 '13 at 17:33