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