The Fibonacci Sequence #
Summary #
Definition of the Fibonacci sequence F₀ = 0, F₁ = 1, Fₙ₊₂ = Fₙ + Fₙ₊₁
.
Main Definitions #
fib
returns the stream of Fibonacci numbers.
Main Statements #
fib_add_two
: shows thatfib
indeed satisfies the Fibonacci recurrenceFₙ₊₂ = Fₙ + Fₙ₊₁.
.fib_gcd
:fib n
is a strong divisibility sequence.
Implementation Notes #
For efficiency purposes, the sequence is defined using stream.iterate
.
Tags #
fib, fibonacci
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.
fib (n + 2)
is strictly monotone.
Subsequent Fibonacci numbers are coprime, see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime
fib n
is a strong divisibility sequence,
see https://proofwiki.org/wiki/GCD_of_Fibonacci_Numbers