## Friday, 16 November 2012

### Closed-form expression

Like every sequence defined by a linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre:[18]
$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$
where

$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots\,$
is the golden ratio (sequence A001622 in OEIS), and
$\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots$
Implement nhanh trên python:

https://github.com/hvnsweeting/FAMILUG/blob/master/Python/fib_o1.py

OUTPUT
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89

Dãy Fibonacci là dãy tổng các đường chéo "lệch" của tam giác Pascal

Và cái clip này chắc ai cũng xem rồi:

[1] http://en.wikipedia.org/wiki/Fibonacci_number

#### 1 comment:

1. ruby: https://github.com/hvnsweeting/FAMILUG/blob/master/ruby/fibfunc.rb