Complex Analysis - Fibonacci Identity

1. Jan 17, 2013

Physics-Pure

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/sabalka/teaching/09Spring375/Chapter10.pdf [Broken]

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 Files:

File size:
1.8 KB
Views:
157
• Capture.PNG
File size:
6 KB
Views:
153
Last edited by a moderator: May 6, 2017
2. Jan 19, 2013

Physics-Pure

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

3. Jan 19, 2013

Physics-Pure

4. Jan 19, 2013

lurflurf

Yes that is Binet's formula.

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

The gain here is the residue at zero is complicated, while the two others lead easily to Binet's formula.

5. Jan 19, 2013

Physics-Pure

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

6. Jan 20, 2013

lurflurf

z^(n-1) is part of the usual formula to extract coefficients from a power series.

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

7. Jan 20, 2013

Physics-Pure

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

8. Jan 20, 2013

Physics-Pure

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

9. Jan 20, 2013

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.

10. Jan 20, 2013

lurflurf

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

11. Jan 20, 2013

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?

12. Jan 20, 2013

Physics-Pure

Why is it even relevant to the question at hand?

13. Jan 20, 2013

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.

14. Jan 20, 2013

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?

15. Jan 20, 2013

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.

16. Jan 20, 2013

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.

17. Jan 20, 2013

Physics-Pure

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

18. Jan 20, 2013

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