Results 1 to 8 of 8

Math Help - Fibonacci numbers from Pascal's triangle

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1

    Fibonacci numbers from Pascal's triangle



    As shown in this picture, you can extract the Fibonacci numbers from Pascal's triangle. I found this equation at mathworld which explained it mathematically:



    But I guess you did already know this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Yes, it was discovered (officially) by Lucas.
    (Though it is not an effcient formula for fibonacci numbers.
    If you discovered that by thyself then good job.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Hehe, no I didn't. I was just googling at Fibonacci numbers or something like that and happened to find it. Then I started to think about how to do to show it's true, but I realized I don't know.

    Another thing you can gather from this is that the "diagonal" sum is growing with an approximate factor of \Phi, the golden ratio, while the horozontal sum in growing with a factor of 2. So when you take n steps withe the diagonal, the factor of growing is \Phi^n, while it would require only x steps for the sum to grow as much if the sum would have been taking from a horitzonal line, where 2^x\ =\ \Phi^n. So x\cdot log(2) = n \cdot log(\Phi)\ \Rightarrow\ x\ =\ \frac{log(\Phi)}{log(2)}\cdot n which means it requires \frac{log(2)}{log(\Phi)} times as many steps to make the diagonal sum grow with as big factor as the horitzonal sum does.

    But I don't know what you can use this to.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by TriKri View Post
    But I don't know what you can use this to.
    You prove it by induction. I am sure it is not bad because I proved it once as an excersice I had in my book. That is why I have seen it before.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Here's an interesting Fibonacci-related item.

    Those familiar with Fibonacci numbers probably know Binet's formula for finding the nth Fibonacci number.

    Here's a way to find out how many digits are in that nth Fibonacci number:

    Of course, you use logs.

    {\phi}=\frac{\sqrt{5}+1}{2}

    log(\frac{{\phi}^{n}}{\sqrt{5}})

    = nlog({\phi})-log(\sqrt{5})

    = nlog({\phi})-\frac{log(5)}{2}....[1]

    Let's try an easy one for a check of the formula:

    Enter n=20 into [1] and we get: 3.83026780283

    The number of digits in a number is 1+the whole part of the log.

    Therefore, there are 4 digits in the 20th Fibonacci number.

    Now, what are those first digits?.

    10 to the power of the frac part of the log.

    10^{0.83026780283}=6.76500002954

    As we can see from Binet's formula or listing them out, the 20th Fibonacci number is 6765.

    Try the 1,000,000th for fun.

    It has 208988 digits and starts with 195..........
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Let me explain it,
    The Binet formula (I derived it on the forum somewhere) is,
    u_n=\frac{\phi^n-\psi^n}{\sqrt{5}}
    Where,
    \psi = \frac{\sqrt{5}-1}{2}
    And,
    \phi = \frac{\sqrt{5}+1}{2}
    Thus, for large n we have,
    \psi^n\approx 0 because 0<\psi<1.
    Thus,
    u_n\approx \frac{\phi^n}{\sqrt{5}}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Here is one more, that I never seen anybody mention before.

    \gcd (u_n,u_m)=u_{\gcd (n,m)}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Let me explain it,
    The Binet formula (I derived it on the forum somewhere) is,
    u_n=\frac{\phi^n-\psi^n}{\sqrt{5}}
    Where,
    \psi = \frac{\sqrt{5}-1}{2}
    And,
    \phi = \frac{\sqrt{5}+1}{2}
    Thus, for large n we have,
    \psi^n\approx 0 because 0<\psi<1.
    Thus,
    u_n\approx \frac{\phi^n}{\sqrt{5}}
    If that's your definition for \psi then I suggest you use -\psi instead:
    u_n=\frac{\phi^n-(-\psi)^n}{\sqrt{5}}

    Btw I think you use to have \varphi for the small value. Then I'm not sure whether the definition is \varphi= \frac{\sqrt{5}-1}{2} or if it is \varphi= \frac{1-\sqrt{5}}{2}. If it is the second, then both values can be derived from the equation x = 1 + \frac{1}{x}, cause then you will get the answer x = \frac{1 \pm \sqrt{5}}{2}. On the other hand, if it is the first definition then both values can be given by the equation x = \frac{\sqrt{5} \pm 1}{2}. Hm, I got the equation can be derived from the equation x^2-\sqrt{5}\cdot x\ =\ -1, or x+\frac{1}{x}\ =\ \sqrt{5}, I wonder where that equation comes from...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pascal-Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 4th 2009, 12:55 PM
  2. Pascal's Triangle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 1st 2008, 11:02 AM
  3. Pascal's triangle
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 4th 2008, 09:37 PM
  4. Pascal's Triangle
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 31st 2007, 07:12 AM
  5. Pascal's Triangle.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 27th 2006, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum