# Fibonacci numbers from Pascal's triangle

• Jan 6th 2007, 09: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, 03: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, 04: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 $\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.
• Jan 6th 2007, 05: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, 06: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.

${\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..........
• Jan 6th 2007, 06:34 PM
ThePerfectHacker
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}}$
• Jan 6th 2007, 06:35 PM
ThePerfectHacker
Here is one more, that I never seen anybody mention before.

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

Originally Posted by ThePerfectHacker
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...