Complex Analysis - Fibonacci Identity


by Physics-Pure
Tags: calculus ii, cauchy integral, complex analysis, fibonacci numbers, residue theorem
Physics-Pure
Physics-Pure is offline
#1
Jan17-13, 03:13 PM
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
Capture2.PNG   Capture.PNG  
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Physics-Pure
Physics-Pure is offline
#2
Jan19-13, 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.
Physics-Pure
Physics-Pure is offline
#3
Jan19-13, 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

lurflurf
lurflurf is offline
#4
Jan19-13, 11:53 PM
HW Helper
P: 2,166

Complex Analysis - Fibonacci Identity


Yes that is Binet's formula.

[tex]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
[/tex]

The gain here is the residue at zero is complicated, while the two others lead easily to Binet's formula.
Physics-Pure
Physics-Pure is offline
#5
Jan19-13, 11:57 PM
P: 29
First off, where does the z^n+1 come from?
But I believe I understand the rest now.
lurflurf
lurflurf is offline
#6
Jan20-13, 12:40 AM
HW Helper
P: 2,166
z^(n-1) 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]
Physics-Pure
Physics-Pure is offline
#7
Jan20-13, 12:46 AM
P: 29
Ahh, I understand. Now why did you put -phi and 1-phi instead of phi and conjuagte phi?
Physics-Pure
Physics-Pure is offline
#8
Jan20-13, 01:01 AM
P: 29
Why would dividing by z^(n+1) extract the a_nth term?
lurflurf
lurflurf is offline
#9
Jan20-13, 01:02 AM
HW Helper
P: 2,166
-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.
lurflurf
lurflurf is offline
#10
Jan20-13, 01:03 AM
HW Helper
P: 2,166
Dividing by z^(n+1) makes the z^n term into z^-1, the residue is the coefficient of z^-1.
Physics-Pure
Physics-Pure is offline
#11
Jan20-13, 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?
Physics-Pure
Physics-Pure is offline
#12
Jan20-13, 01:17 AM
P: 29
Why is it even relevant to the question at hand?
lurflurf
lurflurf is offline
#13
Jan20-13, 01:29 AM
HW Helper
P: 2,166
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.
Physics-Pure
Physics-Pure is offline
#14
Jan20-13, 01:54 AM
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?
Bacle2
Bacle2 is offline
#15
Jan20-13, 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 n-th term.
lurflurf
lurflurf is offline
#16
Jan20-13, 02:12 AM
HW Helper
P: 2,166
[tex]
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}[/tex]

so it does not make much difference. It is just a change of variable between z and -z.
Physics-Pure
Physics-Pure is offline
#17
Jan20-13, 12:12 PM
P: 29
Would you mind showing the work required for (1)? Using the ratio test
lurflurf
lurflurf is offline
#18
Jan20-13, 09:25 PM
HW Helper
P: 2,166
[tex]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}[/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