1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Explicit Formula for the nth Fibonacci Number

  1. Jan 26, 2005 #1
    Problem

    [tex] f(x) = \frac{x}{1-x-x^2} = \sum _{n=1} ^{\infty} f_n x^n [/tex]

    By writing [tex]f(x)[/tex] as a sum of partial fractions, find an explicit formula for the nth Fibonacci number.

    My work

    [tex]\frac{x}{1-x-x^2} = \frac{-4}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1} [/tex]

    Heaviside's method gives:

    [tex] \left. \frac{-4}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{2}{\sqrt{5}} [/tex]

    [tex] \left. \frac{-4}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = -\frac{2}{\sqrt{5}} [/tex]

    Thus,

    [tex] f(x) = \frac{2}{\sqrt{5}} \left( \frac{1}{2x + \sqrt{5} + 1} - \frac{1}{2x - \sqrt{5} + 1} \right) [/tex]

    Then

    [tex] (2x - \sqrt{5} + 1)^{-1} = \frac{1}{1-\sqrt{5}}\left( 1 + \frac{2x}{1-\sqrt{5}} \right) ^{-1} = \frac{1}{1-\sqrt{5}} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{1-\sqrt{5}} \right) ^n = \sum _{n=0} ^{\infty} \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n [/tex]

    [tex] (2x + \sqrt{5} + 1)^{-1} = \frac{1}{\sqrt{5}+1}\left( 1 + \frac{2x}{\sqrt{5}+1} \right) ^{-1} = \frac{1}{\sqrt{5}+1} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{\sqrt{5}+1} \right) ^n = \sum _{n=0} ^{\infty} \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n [/tex]

    [tex]f(x) = \frac{2}{\sqrt{5}} \left\{ \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n \right] - \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n \right] \right\} [/tex]

    What else can I do?

    Thanks
     
    Last edited: Jan 26, 2005
  2. jcsd
  3. Jan 26, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Find a way to combine the two sums into one. :tongue2:
     
  4. Jan 26, 2005 #3
    Yes, I'm a bit confused with such a trivial thing. Let me show you why...

    [tex]f(x) = \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ (-1)^n \left( \frac{2}{ \sqrt{5}+1}} \right) ^{n+1} + (-1)^{n+1} \left( \frac{ 2}{1-\sqrt{5}}}\right) ^{n+1} \right] x^n [/tex]

    I've tested my guess, but it doesn't work. I'm having difficulty combining the changing signs. Could you please explain that? Probably, it's just a lapse. :smile:

    Thanks
     
  5. Jan 26, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Then one of your intermediate steps is wrong! Can you think of a good way to test them?

    BTW, unless I've made an arithmetic error, your final answer works for me...

    (but yes, one of your intermediate steps is wrong)
     
    Last edited: Jan 26, 2005
  6. Jan 26, 2005 #5

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    Redo all your calculations,beginning with the first line,namely the partial fraction decomposition where u miss the "x".That's why you could't retrieve this formula
    where u need to get,formulas #6 & #13

    Daniel.

    P.S.Try to put the radicals to the numerator...
     
  7. Jan 26, 2005 #6

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    HAHAHAHA

    Had to prove this in my exam today, it is so much easier than that but I don't know how to help without giving it all away :confused:
     
  8. Jan 26, 2005 #7

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    Happy Birthday,Zurtex!And yes,you're right,let's let him do the calculations... :smile:


    Daniel.
     
  9. Jan 26, 2005 #8
    I couldn't find a way to have the radicals just in the numerator, but here is what I now have:

    [tex]f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1} [/tex]

    Heaviside's method gives:

    [tex] \left. \frac{-4x}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{-\sqrt{5}}{5}-1 [/tex]

    [tex] \left. \frac{-4x}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = \frac{\sqrt{5}}{5}-1 [/tex]

    Then

    [tex]f(x) = \left( \frac{-\sqrt{5}}{5}-1 \right) \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n \right] + \left( \frac{\sqrt{5}}{5}-1 \right) \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n \right] [/tex]

    Thanks for pointing it out
     
  10. Jan 26, 2005 #9

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    Sorry,i was referring to the last line.The last formula should be "adjusted" as to resemble the famous one which appears on the "wolfram" site...

    Daniel.
     
  11. Jan 26, 2005 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You recall the method of rationalizing the denominator?
     
  12. Jan 26, 2005 #11
    I've just confirmed what I said earlier... memory lapse :rofl:. Anyway...

    [tex]f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = -4x \left( \frac{2x-\sqrt{5}+1}{4x^2 + 4x -4} \right) \left( \frac{2x+\sqrt{5}+1}{4x^2 + 4x -4} \right) = \frac{-4x}{4x^2 + 4x -4} [/tex]

    [tex]f(x) = -4x \left\{ \frac{1}{4x(x+1)} \left[ 1 - \frac{1}{x(x+1)} \right] ^{-1} \right\} = \frac{-1}{x+1} \sum _{n=0} ^{\infty} \binom{-1}{n} \left[ \frac{-1}{x(x+1)} \right] ^n = - \sum _{n=0} ^{\infty} \frac{1}{x^n (x+1)^{n+1}} [/tex]

    There probably is something else that I miss here. :smile:
     
    Last edited: Jan 26, 2005
  13. Jan 27, 2005 #12

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    What did u do here?Where did the radicals go...??

    Daniel.
     
  14. Jan 27, 2005 #13
    I did not use partial fractions at all in my previous post, which is not what I intended to do. By the way, I finally have the solution. :tongue:

    [tex]f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1} [/tex]

    Heaviside's method gives:

    [tex] \left. \frac{-4x}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{-\sqrt{5}}{5}-1 [/tex]

    [tex] \left. \frac{-4x}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = \frac{\sqrt{5}}{5}-1 [/tex]

    Also consider

    [tex] (2x + \sqrt{5} + 1) ^{-1} = \frac{1}{\sqrt{5}+1} \left( 1 + \frac{2x}{\sqrt{5}+1} \right) ^{-1} = \frac{\sqrt{5}-1}{4} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{\sqrt{5}+1} \right) ^n = \frac{\sqrt{5}-1}{4} \sum _{n=0} ^{\infty} \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n [/tex]

    and

    [tex] (2x - \sqrt{5} + 1) ^{-1} = \frac{1}{1-\sqrt{5}} \left( 1 + \frac{2x}{1-\sqrt{5}} \right) ^{-1} = \frac{-\left( 1 + \sqrt{5} \right)}{4} \sum _{n=0} ^{\infty} \binom{-1}{n} \left[ \frac{-\left( 1 + \sqrt{5} \right)}{2} x \right] ^n = \frac{-\left( 1 + \sqrt{5} \right)}{4} \sum _{n=0} ^{\infty} \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n [/tex]

    which allows us to obtain

    [tex]f(x) = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1} = \left( \frac{-\sqrt{5}}{5}-1 \right) \left( \frac{\sqrt{5}-1}{4} \right) \sum _{n=0} ^{\infty} \left[ \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n \right] + \left( \frac{\sqrt{5}}{5}-1 \right) \left[ \frac{-\left( 1 + \sqrt{5} \right)}{4} \right] \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n \right] [/tex]

    [tex]f(x) = \frac{-1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n \right] + \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n \right] = \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n - \left( \frac{1-\sqrt{5}}{2} \right) ^n \right] x^n [/tex]

    Hence, we find

    [tex] F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n - \left( \frac{1-\sqrt{5}}{2} \right) ^n \right] [/tex]

    And again, thank you guys for all the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Explicit Formula for the nth Fibonacci Number
  1. Fibonacci numbers (Replies: 1)

Loading...