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 \, ,\\
   1,               & n=1 \, ,\\ 
   0,               & 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) 
      1 
      (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
      
</code>