Liczby Fibonacciego to ciąg liczb z matematyki nazwany na cześć Leonarda z Pizy, znany jako Fibonacciego. Fibonacci napisał w 1202 roku książkę o nazwie Liber Abaci ("Księga Obliczeń"), która wprowadziła wzór liczbowy do matematyki zachodnioeuropejskiej, choć matematycy w Indiach już o tym wiedzieli.

Pierwsza liczba formacji to 0, druga liczba to 1, a każda następna jest równa dodaniu dwóch liczb tuż przed nią. Na przykład 0+1=1 i 3+5=8. Ta sekwencja trwa wiecznie.

Może to być napisane jako relacja powtarzalności,

F n = F n - 1 + F n - 2 {\i1}=F_{\i1}+F_{\i1}+F_{\i0}} {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

Aby miało to sens, należy podać co najmniej dwa punkty wyjścia. Tutaj, F 0 = 0{\displaystyle F_{0}=0} {\i1}i F 1 = 1 {\i1} {\displaystyle F_{1}=1}{\i1}...{\i1}

Formalna definicja

Rekurencja: dla n ≥ 2 zachodzi

Fn = Fn−1 + Fn−2, z warunkami początkowymi F0 = 0 i F1 = 1.

Uwaga: w literaturze spotyka się także konwencję zaczynającą indeksowanie od 1, gdzie F1=1, F2=1 — to drobna różnica indeksowa, ale struktura ciągu pozostaje taka sama.

Pierwsze wyrazy ciągu

Pierwsze wyrazy (przy konwencji F0=0, F1=1) to:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

Wzory i własności

  • Wzór zamknięty (wzór Bineta):

    Niech φ = (1 + √5)/2 i ψ = (1 − √5)/2. Wtedy

    Fn = (φn − ψn) / √5.

    Dzięki temu wzorowi można obliczyć Fn bez użycia rekurencji.

  • Stosunek sąsiednich wyrazów: stosunek Fn+1/Fn dąży do złotej liczby φ ≈ 1,6180339887... wraz ze wzrostem n.
  • Sumy:
    • Suma pierwszych n wyrazów: ∑k=0n Fk = Fn+2 − 1.
    • Suma kwadratów: ∑k=0n Fk2 = Fn · Fn+1.
  • Własności arytmetyczne: NWD(Fm, Fn) = Fgcd(m,n). Ponadto zachodzi tożsamość Cassiniego:

    Fn+1·Fn−1 − Fn2 = (−1)n.

  • Reprezentacje macierzowe i szybkie algorytmy: właściwości rekurencji pozwalają na obliczanie Fn w czasie logarytmicznym przez szybkie potęgowanie macierzy [[1,1],[1,0]] lub algorytm "fast doubling".

Przykłady obliczeń

  • F6 = F5 + F4 = 5 + 3 = 8.
  • F10 = 55 (ciąg: 0,1,1,2,3,5,8,13,21,34,55).
  • Za pomocą wzoru Bineta: F10 = (φ10 − ψ10)/√5 ≈ 55.

Zastosowania i przykłady w praktyce

  • W przyrodzie: układ liści na łodydze, spirale w szyszkach i skorupkach ślimaków często wykazują związki z liczbami Fibonacciego i złotą proporcją.
  • W informatyce: modelowanie rekurencyjnych funkcji (np. rekurencyjny algorytm obliczania Fibonacciego — przykład, dlaczego należy użyć programowania dynamicznego), struktury danych i algorytmy wykorzystujące szybkie potęgowanie.
  • W sztuce i projektowaniu: złota proporcja (powiązana ze stosunkiem wyrazów ciągu) bywa wykorzystywana do komponowania estetycznych proporcji.

Krótka notka historyczna

Choć ciąg przypisuje się Leonardowi z Pizy (Fibonacciowi) z powodu jego popularyzacji w Europie w "Liber Abaci" (1202), odkrycia i użycie podobnych sekwencji były znane wcześniej w matematyce indyjskiej. Fibonacci przedstawił go m.in. na przykładzie hipotetycznego rozmnażania się par królików, co uczyniło sekwencję znaną szerokiej publiczności.

Jeżeli chcesz, mogę dodać: dowód wzoru Bineta, implementację algorytmu obliczającego Fn w wybranym języku programowania albo tabelę pierwszych N wyrazów ciągu.