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/sabalka/teaching/09Spring375/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

 

[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.

$$A=(z^{n+1}(1-z-z^2))^{-1} \\<br /> 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$$

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.

$$1=^\mathrm{Res}_{z=0}z^{-1}\\<br /> a_n=^\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}\sum_{n=-\infty}^\infty a_n z^n$$

 

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

$$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}$$

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

 

[lurflurf]

$$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}$$

provided we know
$$\lim_{n \rightarrow \infty}\frac{f_{n+1}}{f_n}=\phi$$