English
The Fibonacci sequence is defined by fib(0) = 0, fib(1) = 1, and fib(n+2) = fib(n) + fib(n+1).
Русский
Последовательность Фибоначчи задаётся как fib(0) = 0, fib(1) = 1 и fib(n+2) = fib(n) + fib(n+1).
LaTeX
$$fib(0) = 0, \; fib(1) = 1, \; fib(n+2) = fib(n) + fib(n+1)$$
Lean4
/-- Implementation of the fibonacci sequence satisfying
`fib 0 = 0, fib 1 = 1, fib (n + 2) = fib n + fib (n + 1)`.
*Note:* We use a stream iterator for better performance when compared to the naive recursive
implementation.
-/
@[pp_nodot]
def fib (n : ℕ) : ℕ :=
((fun p : ℕ × ℕ => (p.snd, p.fst + p.snd))^[n] (0, 1)).fst
