# Fibonacci numbers from Pascal's triangle

• Jan 6th 2007, 08:21 AM
TriKri
Fibonacci numbers from Pascal's triangle
http://img364.imageshack.us/img364/8179/pinball5ei8.jpg

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:

http://img482.imageshack.us/img482/391/equation9ym4.gif

But I guess you did already know this.
• Jan 6th 2007, 02:06 PM
ThePerfectHacker
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.
• Jan 6th 2007, 03:53 PM
TriKri
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 $\displaystyle \Phi$, the golden ratio, while the horozontal sum in growing with a factor of 2. So when you take $\displaystyle n$ steps withe the diagonal, the factor of growing is $\displaystyle \Phi^n$, while it would require only $\displaystyle x$ steps for the sum to grow as much if the sum would have been taking from a horitzonal line, where $\displaystyle 2^x\ =\ \Phi^n$. So $\displaystyle x\cdot log(2) = n \cdot log(\Phi)\ \Rightarrow\ x\ =\ \frac{log(\Phi)}{log(2)}\cdot n$ which means it requires $\displaystyle \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.
• Jan 6th 2007, 04:11 PM
ThePerfectHacker
Quote:

Originally Posted by TriKri
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.
• Jan 6th 2007, 05:28 PM
galactus
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.

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

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

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

=$\displaystyle 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.

$\displaystyle 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..........
• Jan 6th 2007, 05:34 PM
ThePerfectHacker
Let me explain it,
The Binet formula (I derived it on the forum somewhere) is,
$\displaystyle u_n=\frac{\phi^n-\psi^n}{\sqrt{5}}$
Where,
$\displaystyle \psi = \frac{\sqrt{5}-1}{2}$
And,
$\displaystyle \phi = \frac{\sqrt{5}+1}{2}$
Thus, for large $\displaystyle n$ we have,
$\displaystyle \psi^n\approx 0$ because $\displaystyle 0<\psi<1$.
Thus,
$\displaystyle u_n\approx \frac{\phi^n}{\sqrt{5}}$
• Jan 6th 2007, 05:35 PM
ThePerfectHacker
Here is one more, that I never seen anybody mention before.

$\displaystyle \gcd (u_n,u_m)=u_{\gcd (n,m)}$
• Jan 6th 2007, 06:46 PM
TriKri
Quote:

Originally Posted by ThePerfectHacker
Let me explain it,
The Binet formula (I derived it on the forum somewhere) is,
$\displaystyle u_n=\frac{\phi^n-\psi^n}{\sqrt{5}}$
Where,
$\displaystyle \psi = \frac{\sqrt{5}-1}{2}$
And,
$\displaystyle \phi = \frac{\sqrt{5}+1}{2}$
Thus, for large $\displaystyle n$ we have,
$\displaystyle \psi^n\approx 0$ because $\displaystyle 0<\psi<1$.
Thus,
$\displaystyle u_n\approx \frac{\phi^n}{\sqrt{5}}$

If that's your definition for $\displaystyle \psi$ then I suggest you use $\displaystyle -\psi$ instead:
$\displaystyle u_n=\frac{\phi^n-(-\psi)^n}{\sqrt{5}}$

Btw I think you use to have $\displaystyle \varphi$ for the small value. Then I'm not sure whether the definition is $\displaystyle \varphi= \frac{\sqrt{5}-1}{2}$ or if it is $\displaystyle \varphi= \frac{1-\sqrt{5}}{2}$. If it is the second, then both values can be derived from the equation $\displaystyle x = 1 + \frac{1}{x}$, cause then you will get the answer $\displaystyle 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 $\displaystyle x = \frac{\sqrt{5} \pm 1}{2}$. Hm, I got the equation can be derived from the equation $\displaystyle x^2-\sqrt{5}\cdot x\ =\ -1$, or $\displaystyle x+\frac{1}{x}\ =\ \sqrt{5}$, I wonder where that equation comes from...