# Thread: Fibonacci numbers from Pascal's triangle

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.

2. 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.

3. 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.

4. 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.

5. 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..........

6. 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}}$

7. Here is one more, that I never seen anybody mention before.

$\displaystyle \gcd (u_n,u_m)=u_{\gcd (n,m)}$

8. 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...