Ciąg Fibonacciego

(Książka Liber abaci opublikowana 1202 roku)

Postać rekurencyjna

F_k = F_k-1 + F_k-2 dla k > 2,

F₁ = F₂ = 1,

Postać iteracyjna

F_k = (a^k + b^k) / √5,

a = (1 + √5)/2 b = (1 - √5)/2,

Liczba słów n bitowych w których nie ma powtórzeń symbolu 0 jest równa F_n+2

Nwd(F_k, F_k-1) = Nwd(F_k-1, F_k-2) = ...

= Nwd(F₂, F₁) = 1

stąd osiągamy złożoność log(F_k)

---