Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complex Analysis - Fibonacci Identity

  1. Jan 17, 2013 #1
    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:

    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Jan 19, 2013 #2
    If anyone knows where to find the solution set, that would also be appreciated. It isn't homework related, simply for fun.
     
  4. Jan 19, 2013 #3
  5. Jan 19, 2013 #4

    lurflurf

    User Avatar
    Homework Helper

    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.
     
  6. Jan 19, 2013 #5
    First off, where does the z^n+1 come from?
    But I believe I understand the rest now.
     
  7. Jan 20, 2013 #6

    lurflurf

    User Avatar
    Homework Helper

    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]
     
  8. Jan 20, 2013 #7
    Ahh, I understand. Now why did you put -phi and 1-phi instead of phi and conjuagte phi?
     
  9. Jan 20, 2013 #8
    Why would dividing by z^(n+1) extract the a_nth term?
     
  10. Jan 20, 2013 #9

    lurflurf

    User Avatar
    Homework Helper

    -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.
     
  11. Jan 20, 2013 #10

    lurflurf

    User Avatar
    Homework Helper

    Dividing by z^(n+1) makes the z^n term into z^-1, the residue is the coefficient of z^-1.
     
  12. Jan 20, 2013 #11
    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?
     
  13. Jan 20, 2013 #12
    Why is it even relevant to the question at hand?
     
  14. Jan 20, 2013 #13

    lurflurf

    User Avatar
    Homework Helper

    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.
     
  15. Jan 20, 2013 #14
    "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?
     
  16. Jan 20, 2013 #15

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  17. Jan 20, 2013 #16

    lurflurf

    User Avatar
    Homework Helper

    [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.
     
  18. Jan 20, 2013 #17
    Would you mind showing the work required for (1)? Using the ratio test
     
  19. Jan 20, 2013 #18

    lurflurf

    User Avatar
    Homework Helper

    [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$$
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Complex Analysis - Fibonacci Identity
  1. Complex analysis (Replies: 1)

Loading...