# Complex Analysis - Fibonacci Identity

by Physics-Pure
Tags: calculus ii, cauchy integral, complex analysis, fibonacci numbers, residue theorem
 P: 29 Hey guys~ I was looking for a way to derive a formula for fn (the nth term in the fibonacci sequence). While looking for this, I came across a potential solution using the residue theorem. Using the generating function Ʃk≥0 fnzn, find the identity for fn. The problem looks like the right thumbnail. Also, it can be found here on page 106: http://www.math.binghamton.edu/sabal.../Chapter10.pdf I personally do not understand how using the suggested hint will bring you to a formula for fn. I know that one must Recall Cauchy's integral formula to relate the integral to the value of fn. Also, will the resulting identity simply be Binet's formula? Thanks all, Physics-Pure Attached Thumbnails
 P: 29 If anyone knows where to find the solution set, that would also be appreciated. It isn't homework related, simply for fun.
 P: 29 If you would like to see my work thus far on this problem set look here: http://math.stackexchange.com/q/282436/58540
HW Helper
P: 2,168

## Complex Analysis - Fibonacci Identity

Yes that is Binet's formula.

$$A=(z^{n+1}(1-z-z^2))^{-1} \\ f_n=^\mathrm{Res}_{z=0}A=\left(^\mathrm{Res}_{z=-\phi}A+^\mathrm{Res}_{z=0}A+^\mathrm{Res}_{z=1-\phi}A \right)-^\mathrm{Res}_{z=-\phi}A-^\mathrm{Res}_{z=1-\phi}A=\frac{1}{2\pi i}\oint \! A \mathrm \,{dz}-^\mathrm{Res}_{z=-\phi}A-^\mathrm{Res}_{z=1-\phi}A=-^\mathrm{Res}_{z=-\phi}A-^\mathrm{Res}_{z=1-\phi}A$$

The gain here is the residue at zero is complicated, while the two others lead easily to Binet's formula.
 P: 29 First off, where does the z^n+1 come from? But I believe I understand the rest now.
 HW Helper P: 2,168 z^(n-1) is part of the usual formula to extract coefficients from a power series. $$1=^\mathrm{Res}_{z=0}z^{-1}\\ a_n=^\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}\sum_{n=-\infty}^\infty a_n z^n$$
 P: 29 Ahh, I understand. Now why did you put -phi and 1-phi instead of phi and conjuagte phi?
 P: 29 Why would dividing by z^(n+1) extract the a_nth term?
 HW Helper P: 2,168 -phi and 1-phi are the roots of 1-z-z^2 phi and conjuagte phi are the roots of 1-z+z^2 It works out the same in the end.
 HW Helper P: 2,168 Dividing by z^(n+1) makes the z^n term into z^-1, the residue is the coefficient of z^-1.
 P: 29 Alright. Can you also tell me why it's even useful to show that it has a positive radius of convergence? And how to do so?
 P: 29 Why is it even relevant to the question at hand?
 HW Helper P: 2,168 The positive radius of convergence can be found many ways including by the ratio test if you can find the limiting ratio. A positive radius of convergence tells us F is nonsingular at z=0 which we use in extracting the coefficients. If F had a pole we would need to ajust the coefficients, if F had an essential singularity it might be much harder.
 P: 29 "phi and conjuagte phi are the roots of 1-z+z^2 It works out the same in the end." Why does it work out the same in the end?
 Sci Advisor P: 1,168 Another approach is that of describing the regression as a matrix, and then diagonalizing the matrix ( not too hard to show it is diagonalizable). That gives you a closed form for the n-th term.
 HW Helper P: 2,168 $$f_n=^\mathrm{Res}_{z=0}(z^{n+1}(1-z-z^2))^{-1}=^\mathrm{Res}_{z=0}((-z)^{n+1}(-1-z+z^2))^{-1}$$ so it does not make much difference. It is just a change of variable between z and -z.
 P: 29 Would you mind showing the work required for (1)? Using the ratio test
 HW Helper P: 2,168 $$r^{-1}=\lim_{n \rightarrow \infty} \left|\frac{f_{n+1}}{f_n}\right|=\lim_{n \rightarrow \infty} \left|\frac{f_n+f_{n-1}}{f_n}\right|=\lim_{n \rightarrow \infty} \left|1+\frac{f_{n-1}}{f_n}\right|= 1+\phi^{-1}=\phi \\ r=\phi^{-1}$$ provided we know $$\lim_{n \rightarrow \infty}\frac{f_{n+1}}{f_n}=\phi$$

 Related Discussions General Math 0 Linear & Abstract Algebra 2 Calculus 0 Calculus & Beyond Homework 1 Linear & Abstract Algebra 2