Complex Analysis - Fibonacci Identity

Physics-Pure

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_nzⁿ, 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,
Physics-Pure

Attached Thumbnails

   

Physics-Pure

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

Physics-Pure

If you would like to see my work thus far on this problem set look here: http://math.stackexchange.com/q/282436/58540

lurflurf

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

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

lurflurf

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

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

Physics-Pure

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

lurflurf

-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

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

Physics-Pure

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

Why is it even relevant to the question at hand?

lurflurf

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

"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

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

[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

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