Complex Analysis  Fibonacci Identityby PhysicsPure Tags: calculus ii, cauchy integral, complex analysis, fibonacci numbers, residue theorem 

#1
Jan1713, 03:13 PM

P: 29

Hey guys~
I was looking for a way to derive a formula for f_{n} (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 f_{n}z^{n}, find the identity for f_{n}. 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 f_{n}. 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, PhysicsPure 



#2
Jan1913, 03:15 PM

P: 29

If anyone knows where to find the solution set, that would also be appreciated. It isn't homework related, simply for fun.




#3
Jan1913, 09:06 PM

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




#4
Jan1913, 11:53 PM

HW Helper
P: 2,148

Complex Analysis  Fibonacci Identity
Yes that is Binet's formula.
[tex]A=(z^{n+1}(1zz^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 [/tex] The gain here is the residue at zero is complicated, while the two others lead easily to Binet's formula. 



#5
Jan1913, 11:57 PM

P: 29

First off, where does the z^n+1 come from?
But I believe I understand the rest now. 



#6
Jan2013, 12:40 AM

HW Helper
P: 2,148

z^(n1) is part of the usual formula to extract coefficients from a power series.
[tex]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[/tex] 



#7
Jan2013, 12:46 AM

P: 29

Ahh, I understand. Now why did you put phi and 1phi instead of phi and conjuagte phi?




#8
Jan2013, 01:01 AM

P: 29

Why would dividing by z^(n+1) extract the a_nth term?




#9
Jan2013, 01:02 AM

HW Helper
P: 2,148

phi and 1phi are the roots of 1zz^2
phi and conjuagte phi are the roots of 1z+z^2 It works out the same in the end. 



#10
Jan2013, 01:03 AM

HW Helper
P: 2,148

Dividing by z^(n+1) makes the z^n term into z^1, the residue is the coefficient of z^1.




#11
Jan2013, 01:14 AM

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?




#12
Jan2013, 01:17 AM

P: 29

Why is it even relevant to the question at hand?




#13
Jan2013, 01:29 AM

HW Helper
P: 2,148

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.




#14
Jan2013, 01:54 AM

P: 29

"phi and conjuagte phi are the roots of 1z+z^2
It works out the same in the end." Why does it work out the same in the end? 



#15
Jan2013, 02:07 AM

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 nth term.




#16
Jan2013, 02:12 AM

HW Helper
P: 2,148

[tex]
f_n=^\mathrm{Res}_{z=0}(z^{n+1}(1zz^2))^{1}=^\mathrm{Res}_{z=0}((z)^{n+1}(1z+z^2))^{1}[/tex] so it does not make much difference. It is just a change of variable between z and z. 



#17
Jan2013, 12:12 PM

P: 29

Would you mind showing the work required for (1)? Using the ratio test




#18
Jan2013, 09:25 PM

HW Helper
P: 2,148

[tex]r^{1}=\lim_{n \rightarrow \infty} \left\frac{f_{n+1}}{f_n}\right=\lim_{n \rightarrow \infty} \left\frac{f_n+f_{n1}}{f_n}\right=\lim_{n \rightarrow \infty} \left1+\frac{f_{n1}}{f_n}\right= 1+\phi^{1}=\phi \\ r=\phi^{1}[/tex]
provided we know $$\lim_{n \rightarrow \infty}\frac{f_{n+1}}{f_n}=\phi$$ 


Register to reply 
Related Discussions  
[complex analysis] domain coloring applet? (visualizing complex functions)  General Math  0  
I've never felt dumber: please help me understand Fibonacci identity.  Linear & Abstract Algebra  2  
Identity in complex analysis  Calculus  0  
The identity theroem complex analysis  Calculus & Beyond Homework  1  
Help with Fibonacci Identity  Linear & Abstract Algebra  2 