Register to reply

Complex Analysis - Fibonacci Identity

Share this thread:
Physics-Pure
#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
Mysterious source of ozone-depleting chemical baffles NASA
Water leads to chemical that gunks up biofuels production
How lizards regenerate their tails: Researchers discover genetic 'recipe'
Physics-Pure
#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
#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
#4
Jan19-13, 11:53 PM
HW Helper
P: 2,264
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
#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
#6
Jan20-13, 12:40 AM
HW Helper
P: 2,264
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
#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
#8
Jan20-13, 01:01 AM
P: 29
Why would dividing by z^(n+1) extract the a_nth term?
lurflurf
#9
Jan20-13, 01:02 AM
HW Helper
P: 2,264
-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
#10
Jan20-13, 01:03 AM
HW Helper
P: 2,264
Dividing by z^(n+1) makes the z^n term into z^-1, the residue is the coefficient of z^-1.
Physics-Pure
#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
#12
Jan20-13, 01:17 AM
P: 29
Why is it even relevant to the question at hand?
lurflurf
#13
Jan20-13, 01:29 AM
HW Helper
P: 2,264
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
#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
#15
Jan20-13, 02:07 AM
Sci Advisor
P: 1,169
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
#16
Jan20-13, 02:12 AM
HW Helper
P: 2,264
[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
#17
Jan20-13, 12:12 PM
P: 29
Would you mind showing the work required for (1)? Using the ratio test
lurflurf
#18
Jan20-13, 09:25 PM
HW Helper
P: 2,264
[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