Differences

This shows you the differences between two versions of the page.

--- fibonacci_series [2007-07-16 17:00] – nik
+++ fibonacci_series [2026-02-11 12:09] (current) – nik
@@ Line 1: / Line 1: @@
+The Fibonacci numbers 0,1,1,2,3,5,8,13,21,34,… are generated by the following simple rule
+$$F_n =
+ \begin{cases}
+   F_{n-1}+F_{n-2}, & n>1 \, ,\\
+,               & n=1 \, ,\\
+,               & n=0 \, .\\
+ \end{cases}$$
+====Closed-form expression====
+(aka Bernoulli or Binet's formula)
+$$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$$
+Since $\psi = -\varphi^{-1}$, Binet's formula can also be written as
+$$F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi)^{-n}}{2\varphi - 1}$$
+Binet's formula extended to real numbers.
+$$F_n = \frac{\varphi^n - \varphi^{-n}}{2^n \sqrt{5}}$$
+<code python>
+phi = 1 + sqrt(5)
+psi = 1 - sqrt(5)
+def Fibonacci(n):
+    return int((phi**n - psi**n) / (2**n * sqrt(5)))
+</code>
+====Recursively...====
 <code lisp>
 (defun fibonacci (n)
   (if (<= n 2)
       (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
 </code>