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
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
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,263
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,263
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,263
-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,263
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,263
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,263
[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,263
[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