4.* Ciąg Fibonacciego (DODATEK) - M_R_W16_M1 Własności ciągów

R1Y6b5jlIWEZT

4. Ciąg Fibonacciego

RqGAwOX096URT1

Zdjęcie przedstawia rzeźby. Na pierwszym planie jest posąg Fibonnaciego w kolorze białym, w tle znajdują się inne rzeźby i malowidła ścienne. — Fibonacci
Źródło: dostępny w internecie: commons.wikimedia.org, licencja: CC BY 2.5.

Leonardo Bogollo, zwany też Fibonaccim (co oznacza syn Bonacciego) to dwunastowieczny włoski matematyk, uważany za najbardziej utalentowanego zachodniego matematyka średniowiecza. Fibonacci spopularyzował w Europie arabski system liczbowy.

Znany jest jako autor ciągu liczbowego, za pomocą którego rozwiązał problem polegający na wzroście populacji królików w oparciu o wyidealizowane założenia.

Na budowie tego ciągu, zwanego obecnie oczywiście ciągiem Fibonacciego, wzorowała się przez wieki rzesza matematyków, poszukująca między innymi uniwersalnego wzoru określającego liczby pierwsze.

RibfsNnCYTo8o

Zdjęcie przedstawia halę dworcową. Na pierwszym planie znajdują się ludzie, tablice z rozkładami jazdy oraz zegar. W tle pokazane jest okno. Na oknie znajdują się neony ułożone w kształt spirali w kolorze czerwonym. — Liczby Fibonacciego w Zürich Hauptbahnhof
Źródło: dostępny w internecie: commons.wikimedia.org, domena publiczna.

Wyrazy ciągu Fibonacciego są też inspiracją dla malarzy, architektów, a nawet muzyków.

W tym materiale poznamy bliżej ten ciąg i jego zastosowania matematyczne. Niektóre treści wykraczają poza wskazane w podstawie programowej – potraktuj je więc jako ciekawostki lub wiadomości przeznaczone dla wyjątkowo zainteresowanych problemem.

Twoje cele

Utworzysz kolejne liczby Fibonacciego.
Wyznaczysz wyrazy ciągu Fibonacciego na podstawie wzoru rekurencyjnego.
Odkryjesz i zastosujesz niektóre własności ciągu Fibonacciego.
Zauważysz regularności, podobieństwa oraz analogie i na ich podstawie sformułujesz wnioski i uzasadnisz ich poprawność.

Liczby Fibonacciego tworzone są w ten sposób, że każda następna liczba (począwszy od czwartej liczby ciągu, czyli liczby o numerze $3$ ) jest sumą dwóch liczb bezpośrednio ją poprzedzających. Przy czym najmniejsza liczba to $0$ , a dwie następne to $1$ i $1$ .

Zatem liczby o numerach $0$ , $1$ , $2$ to odpowiednio $0$ , $1$ , $1$

Liczba o numerze $3$ to $1 + 1$ , czyli $2$ .

Liczba o numerze $4$ to $1 + 2$ , czyli $3$ .

Liczba o numerze $5$ to $2 + 3$ , czyli $5$ .

Itd.

Ciąg Fibonacciego $(F_{n})$ , to ciąg (określony w zbiorze wszystkich liczb naturalnych), którego wyrazami są kolejne liczby Fibonacciego:

R7mSlo2TvNpZx

Grafika przedstawia zestawienie liczb naturalnych z kolejnymi elementami ciągu Fibonacciego. Tabela zbudowana jest z 2 wierszy. W górnym wierszu znajdują się liczby naturalne n. W dolnym wierszu umieszczone są kolejne wartości ciągu Fibonacciego. Liczby naturalne przyporządkowano wartościom ciągu Fibonacciego. Przyporządkowanie jest następujące: 0 z 0, 1 z 1, 2 z 1, 3 z 2, 4 z 3, 5 z 5, 6 z 8, 7 z 13, 8 z 21, 9 z 34, 10 z 55, 11 z 89, 12 z 144, 13 z 233 oraz 14 z 377. Zestawienie zakończone jest trzykropkiem, gdyż liczby naturalne oraz ciąg Fibonacciego ciągną się w nieskończoność. Pod tabelą pokazane zostało równanie: 5 plus 8 równa się 13. Równanie pokazuje sposób tworzenia kolejnych elementów ciągu Fibonacciego.

Liczby Fibonacciego odegrały znaczącą rolę w rozwoju teorii liczb, a także w rozwoju innych dziedzin wiedzy matematycznej. Doceniając ich znaczenie, dzień $23$ listopada ustanowiono Dniem Fibonacciego ( $1$ , $1$ i $2$ , $3$ to kolejne liczby Fibonacciego).

Przykład 1

Znajdziemy wyraz $F_{15}$ ciągu Fibonacciego.

Skorzystamy z przedstawionej powyżej tabelki, z której odczytamy wyrazy $F_{13}$ i $F_{14}$ .

$F_{15} = F_{13} + F_{14}$

$F_{15} = 233 + 377 = 610$

Ciąg Fibonacciego $(F_{n})$ najłatwiej jest zdefiniować rekurencyjnie:

F_{n} = \{\begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n - 1} + F_{n - 2}, & n > 1 \end{cases}

Ciąg ten można też definiować pomijając wyraz równy $0$ , wtedy wzór rekurencyjny ciągu jest następujący:

F_{n} = \{\begin{cases} 1, & n = 1 \\ 1, & n = 2 \\ F_{n - 1} + F_{n - 2}, & n > 2 \end{cases}

RxyXkFmtBvflz

Grafika przedstawia powstawanie ciągu kwadratów, których długości boków są kolejnymi liczbami ciągu Fibonacciego. Przedstawione zostało 6 kroków, w których dodawane są kolejne kwadraty aż do uzyskania kwadratu o długości boku 8. Krok 1: mały kwadrat z cyfrą 1, o długości boku 1. Krok 2: 2 kwadraty tej samej wielkości oznaczone cyfrą 1 złączone ze sobą bokami. Krok 3: 2 kwadraty tej samej wielkości z cyfrą 1 złączone ze sobą bokami, oraz przylegający od spodu kwadrat o długości boku równej dwóm mniejszym kwadratom. Krok 4: Do istniejących już kwadratów z lewej strony dodany został kwadrat o boku równym jednemu kwadratowi z liczbą 1 i kwadratowi z liczbą 2, zatem długość boku tego kwadratu jest równa 3. Krok 5: Do narysowanych już kwadratów dodany został kwadrat z liczbą 5, który od góry przylega do dwóch kwadratów z wartością jeden oraz kwadratu z wartością 3, zatem długość jego boku to 5. Krok 6: Z prawej strony istniejących kwadratów pojawia się kwadrat z liczbą 8. Przylega on do kwadratu z cyfrą 5, jednego kwadratu z cyfrą 1 i kwadratu z cyfrą 2, długość boku tego kwadratu to 8. — Ciąg kwadratów, których długości boków są kolejnymi liczbami ciągu Fibonacciego

Wyrazy ciągu Fibonacciego mają wiele ciekawych własności. Niektóre z nich przedstawiono w poniższych przykładach.

Przykład 2

Wyrazy ciągu Fibonacciego – własności
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$	$55$	$89$	$144$	$233$

Zaobserwujmy podzielność wyrazów ciągu Fibonacciego.
Co trzeci wyraz ciągu Fibonacciego jest podzielny przez $2$ , począwszy od wyrazu $F_{3} = 2$ .

Co czwarty wyraz ciągu Fibonacciego jest podzielny przez $3$ , począwszy od wyrazu $F_{4} = 3$ .

Co piąty wyraz ciągu Fibonacciego jest podzielny przez $5$ , począwszy od wyrazu $F_{5} = 5$ .

Przykład 3

Określimy jeszcze kilka własności wyrazów ciągu Fibonacciego. Suma dowolnych dziesięciu kolejnych wyrazów ciągu Fibonacciego (pierwszą dziesiątkę liczb rozpoczynamy od wyrazu $F_{1}$ ) jest podzielna przez $11$ .

Wyraz ciągu Fibonacciego równy kwadratowi swojego indeksu to $F_{12} = 12^{2} = 144$ .

Największy znany wyraz ciągu Fibonacciego składający się z cyfr nieparzystych to $F_{22} = 17711$ .

Niektóre liczby Fibonacciego to liczby pierwsze np. $2$ , $3$ , $5$ , $13$ , $89$ , $233$ , $. . .$
Prawdopodobnie tych liczb w ciągu jest nieskończenie wiele.

Każdą liczbę naturalną można przedstawić jako sumę liczb Fibonacciego.
Np.
$1000000 = 832040 + 121393 + 46368 + 144 + 55$
$1000000 = F_{30} + F_{26} + F_{24} + F_{12} + F_{10}$ .

Przykład 4

Ciąg Fibonacciego można opisać wzorem ogólnym $F_{n} = \frac{{(1 + \sqrt{5})}^{n} - {(1 - \sqrt{5})}^{n}}{2^{n} \cdot \sqrt{5}}$ .

Obliczymy na podstawie tego wzoru $F_{3}$ .

$F_{3} = \frac{{(1 + \sqrt{5})}^{3} - {(1 - \sqrt{5})}^{3}}{2^{3} \cdot \sqrt{5}}$

$F_{3} = \frac{(1 + 3 \sqrt{5} + 3 \sqrt{25} + 5 \sqrt{5}) - (1 - 3 \sqrt{5} + 3 \sqrt{25} - 5 \sqrt{5})}{8 \cdot \sqrt{5}}$

$F_{3} = \frac{16 \sqrt{5}}{8 \sqrt{5}} = 2$

Pokażemy teraz zastosowanie liczb Fibonacciego w obliczeniach kombinatorycznych.

Przykład 5

Mamy do dyspozycji płyty o wymiarach $2 \times 1$ . Chcemy nimi wyłożyć plac o wymiarach $2 \times n$ , gdzie $n \in ℕ$ . Niech $a_{n}$ będzie liczbą różnych pokryć tego placu płytami.

Na rysunku pokazane są sposoby ułożenia płyt na placu o wymiarach odpowiednio $2 \times 1$ , $2 \times 2$ , $2 \times 3$ .

R1BjIpTYwGQw2

Rysunek przedstawia sposób ułożenia płyt na polach o wymiarach podanych w zadaniu. Najpierw pokazany jest prostokąt o stosunku boków 2 do 1, gdzie krótszy bok ustawiony jest poziomo, a dłuższy pionowo. Jest pod nim podpis: a, dolny indeks, 1, równa się 1. Następnie przedstawione zostały 2 sposoby ułożenia dwóch prostokątów o stosunku boków 2 do 1. Pierwszy sposób: 2 prostokąty przylegające do siebie dłuższymi bokami, gdzie dłuższy bok ma orientację pionową. Drugi sposób: 2 prostokąty połączone dłuższymi bokami, gdzie dłuższy bok ma orientację poziomą. Pod rysunkami znajduje się napis: a, dolny indeks, 2, równa się 2. Na końcu pokazane zostały 3 sposoby ułożenia trzech prostokątów. Sposób pierwszy: 3 prostokąty, przylegające do siebie dłuższymi bokami, gdzie dłuższy bok ma orientację pionową. Drugi sposób: 1 prostokąt, jest ustawiony tak, że jego dłuższy bok ma orientację pionową. Do jego dłuższego boku z prawej strony przylegają krótszymi bokami dwa połączone ze sobą dłuższym bokiem prostokąty. Dłuższe boki dwóch prostokątów mają orientację poziomą. Ostatni sposób jest odbiciem lustrzanym sposobu drugiego. Pod ostatnimi trzema sposobami jest podpis: a, dolny indeks, 3, równa się 3.

Przyjmujemy też, że $a_{0} = 1$ .

Wykażemy, że dla każdej liczby naturalnej $n \geq 3$ prawdziwa jest równość

$a_{n} = a_{n - 2} + a_{n - 1}$

Dowód:

Jeśli należy pokryć plac płytami o wymiarach $2 \times n$ , to płytę możemy położyć pionowo lub poziomo.

RpzdIUl2x6TlU

Grafika przedstawia dwa szeregi kwadratów. Oba szeregi składają się z dwóch wierszy, a w każdym wierszu znajduje się dziewięć kwadratów, przy czym ostatnia para kwadratów oddzielona jest od reszty trzykropkiem, co oznacza że w rzeczywistości szereg składa się z większej ilości elementów niż zostało pokazane na rysunku. W pierwszym szeregu dwa pierwsze kwadraty w każdym wierszu zostały połączone i zamalowane na zielono. Dzięki czemu powstały dwa prostokąty o wysokości jednego kwadratu i długości dwóch kwadratów. Połączone ze sobą dłuższym bokiem, których krótszy bok ma orientację poziomą. W drugim szeregu zamalowane zostały po jednym kwadracie w każdym wierszu. Dzięki czemu powstał jeden prostokąt o szerokości jednego kwadratu i wysokości dwóch kwadratów. Jego dłuższy bok ma orientację pionową.

Jeżeli płyta na pierwszym polu leży poziomo to należy pokryć pozostałą część placu o wymiarach $2 \times (n - 2)$ . Jest $a_{n - 2}$ możliwości tego dokonania.

Jeżeli płyta leży pionowo, to należy pokryć pozostałą część placu o wymiarach $2 \times (n - 1)$ . Jest $a_{n - 1}$ możliwości tego dokonania.

Dodając te liczby, otrzymujemy

$a_{n} = a_{n - 2} + a_{n - 1}$

Zauważmy, że dla każdej liczby naturalnej $n$

$a_{n} = F_{n + 1}$

Rzeczywiście,

$a_{1} = 1 = F_{2}$

$a_{2} = 2 = F_{3}$

oraz ta sama zasada rekurencjizasada rekurencji obowiązuje dla ciągu $(a_{n})$ i $(F_{n})$ zatem $a_{n} = F_{n + 1}$ .

Przykład 6

Przyjrzyjmy się zależności między trzema kolejnymi wyrazami ciągu Fibonacciego.

RQyHFGqsZ6t7e

Grafika przedstawia dwa grafy. Pierwszy z nich rozpoczyna się od 7 kwadratów, gdzie pierwsze 5 jest oznaczone liczbami kolejno: 2, 3, 5, 8, 13, a dwa ostatnie są puste. Bezpośrednio pod kwadratem z cyfrą5 pięć znajduje się kwadrat z napisem: 5 do potęgi 2. Jest on połączony ze znajdującym się po prawej stronie kwadratem z liczbą 25. Poniżej kwadratu z napisem: 5 do potęgi 2 znajduje się prostokąt z lewą stroną równania trzy razy 8. Cyfry 3 i 8 znajdujące się w kwadratach są połączone z częścią równania za pomocą linii. Lewa strona równania jest również połączona z znajdującym się po prawej stronie wynikiem liczbą 24. Nad kwadratem z liczbą 24 zapisana została liczba minus 1. Pod pierwszym grafem zapisane są równania: 25, minus 1, równa się, 3, razy,8. F, dolny indeks, 5, minus 1, równa się, F, dolny indeks, 4, razy, F, dolny indeks,6. Drugi graf również rozpoczyna się od siedmiu kwadratów, gdzie pierwsze pięć jest oznaczone liczbami kolejno: 3, 5, 8, 13, 21, a dwa ostatnie kwadraty są puste. Bezpośrednio pod kwadratem z cyfrą 8 znajduje się kwadrat z napisem: 8 do potęgi 2, który jest połączony z znajdującą się po prawej stronie liczbą 64. Poniżej napisu, znajduje się lewa część równania: 5, razy, 13, a jego wynik pokazany jest po prawej stronie jest równy 65. Nad liczbą 65 jest zapisana liczba plus 1. Pod drugim grafem zapisane zostały równania: 64, dodać,1, równa się,5, razy,13. Oraz F, dolny indeks, 6, dodać, 1, równa się, F, dolny indeks, 5, razy, F, dolny indeks, 7.

Wniosek:

Jeśli dane są trzy kolejne wyrazy ciągu Fibonacciego to kwadrat wyrazu środkowego, odpowiednio zwiększony bądź zmniejszony o $1$ jest równy iloczynowi wyrazów sąsiednich.

$F_{n}^{2} - {(- 1)}^{n - 1} = F_{n - 1} \cdot F_{n + 1}$

Ciąg Fibonacciego można określić też dla indeksów ujemnych.

$F_{n - 2} = F_{n} - F_{n - 1}$

Czyli

$F_{(- n)} = {(- 1)}^{n + 1} \cdot F_{n}$

Ciąg Fibonacciego dla indeksów ujemnych i dodatnich
$n$	$. . .$	$- 6$	$- 5$	$- 4$	$- 3$	$- 2$	$- 1$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$. . .$
$F_{n}$	$. . .$	$- 8$	$5$	$- 3$	$2$	$- 1$	$1$	$0$	$1$	$1$	$2$	$3$	$5$	$8$	$. . .$

Przykład 7

Obliczymy wyraz $F_{(- 8)}$ ciągu Fibonacciego.

Skorzystamy ze wzoru

$F_{(- n)} = {(- 1)}^{n + 1} \cdot F_{n}$

$F_{(- 8)} = {(- 1)}^{8 + 1} \cdot F_{8}$

$F_{(- 8)} = (- 1) \cdot 21 = - 21$ .

Polecenie 1

Zapoznaj się z filmem edukacyjnym pokazującym niektóre własności liczb Fibonacciego.

RKPtg2FWTlWYB

Polecenie 2

Rozwiąż problem postawiony przez Leonarda Fibonacciego:

Ile par królików może powstać z jednej pary królików w ciągu roku, jeżeli:

każda para królików rodzi nową parę w ciągu miesiąca,

nowa para staje się płodna po upływie miesiąca,

króliki nie umierają.

Miesiąc $1$ – liczba par $1$

Miesiąc $2$ – liczba par $1$

Miesiąc $3$ – liczba par $2$

Miesiąc $4$ – liczba par $3$

Miesiąc $5$ – liczba par $5$

Miesiąc $6$ – liczba par $8$

Miesiąc $7$ – liczba par $13$

$\dots$

Liczby par w kolejnych miesiącach to kolejne wyrazy ciągu Fibonacciego.

Zatem $F_{12} = 144$ .

Odpowiedź:

Liczba par królików po roku to $144$ .

Pokaż ćwiczenia:

RA91uGg0C3WG21

Ćwiczenie 1

Ćwiczenie 2

Przyrost gałęzi pewnego drzewa w okresie kolejnych miesięcy zwiększa się w określony sposób. Liczbę gałęzi określają kolejne liczby Fibonacciego.

R1YNmiWHjhvLh

Grafika przedstawia drzewo w kolorze czerwonym. Cały rysunek jest podzielony na 6 równych pól za pomocą poziomych linii. Po prawej stronie zapisane są kolejne liczby ciągu Fibonacciego. Kolejno od dołu: 1, 2, 3, 5, 8, 13. W pierwszym polu na samym dole rysunku jest tylko pień drzewa. W drugim polu drzewo rozdziela się na dwie grube odnogi. W trzecim polu z prawej odnogi wyrasta dodatkowa gałąź. W czwartym polu z lewej odnogi wyrasta dodatkowa gałąź, natomiast prawa odnoga dzieli się już na trzy gałęzie. W tym polu w sumie znajduje się 5 gałęzi. W piątym polu Z lewej odnogi wyrastają 3 gałęzie, a prawa dzieli się na 5 gałęzi. W szóstym polu lewa odnoga dzieli się na pięć gałęzi, a prawa odnoga dzieli się na 8 gałęzi.

RViZlu4iPhmPC

R1HfnAR56L8E52

Ćwiczenie 3

RctqCujgmmYfX

Ćwiczenie 3

R1WGabTs4nxEd2

Ćwiczenie 4

Ćwiczenie 5

Oblicz, na ile różnych sposobów można ułożyć chodnik o długości $n$ i szerokości $1$ , mając do dyspozycji płyty o wymiarach $1 \times 1$ i $1 \times 2$ .

Oznaczmy przez $a_{n}$ liczbę sposobów wyboru płyt.

RSCh2vusDxZR1

Rysunek przedstawia szereg dziesięciu kwadratów, przy czym pierwszy kwadrat jest zamalowany na kolor szary, a następne dziewięć niezamalowanych kwadratów jest objęte klamrą z podpisem n minus 1.

Dla $n \geq 2$ chodnik można zacząć układać od płyty o wymiarach $1 \times 1$ . Wtedy pozostałe płyty można ułożyć na $a_{n - 1}$ sposobów.

RiZEvwjw4SxlT

Rysunek przedstawia szereg dziesięciu kwadratów, przy czym pierwsze dwa kwadraty są zamalowane na kolor szary, a następne osiem niezamalowanych kwadratów jest objęte klamrą z podpisem n minus 2.

Dla $n \geq 3$ chodnik można zacząć układać od płyty o wymiarach $1 \times 2$ . Wtedy pozostałe płyty można ułożyć na $a_{n - 2}$ sposobów.

Stąd $a_{n} = a_{n - 2} + a_{n - 1}$ dla $n \geq 3$ .

Otrzymany wzór jest taki sam, jak dla ciągu Fibonacciego.

Zauważmy przy tym, że:

$a_{1} = 1 = F_{2}$

$a_{2} = 2 = F_{3}$

Zatem

$a_{n} = F_{n + 1}$

RWn8W6ow1EiTG2

Ćwiczenie 6

Ćwiczenie 7

Sprawdź na kilku przykładach, że dowolny wyraz ciągu Fibonacciego można przedstawić w poniższej postaci. Znajdź w dostępnych źródłach dowód tego twierdzenia.

$F_{n} = \frac{1}{\sqrt{5}} \cdot [{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}]$

Wzór ten, zwany jest wzorem Bineta. Dla n = 3 prawdziwość tego wzoru została sprawdzona w sekcji Przeczytaj.

Dowód tego wzoru jest dość trudny. Zwykle opiera się na zauważeniu, że rozwiązując równanie kwadratowe

$x^{2} - x - 1 = 0$

otrzymujemy

$x_{1} = \frac{1 - \sqrt{5}}{2}$ , $x_{2} = \frac{1 + \sqrt{5}}{2}$

Wynika z tego, że

$F_{n} = a {(\frac{1 - \sqrt{5}}{2})}^{n} + b {(\frac{1 + \sqrt{5}}{2})}^{n}$

Współczynniki $a$ , $b$ otrzymamy, korzystając z wartości pierwszych dwóch wyrazów ciągu.

$F_{0} = a + b = 0$ i $F_{1} = a {(\frac{1 - \sqrt{5}}{2})}^{1} + b {(\frac{1 + \sqrt{5}}{2})}^{1} = 1$

Stąd

$a = - b = \frac{1}{\sqrt{5}}$

Czyli

$F_{n} = \frac{1}{\sqrt{5}} \cdot [{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}]$

co należało udowodnić.

Ćwiczenie 8

Dla ciągu $(F_{n})$ prawdziwy jest wzór

$F_{n} = \frac{F_{n + 5} - F_{n - 5}}{11}$ dla $n \geq 5$ .

Sprawdź prawdziwość tego wzoru dla $n = 10$ .

$L = F_{10} = 55$

$P = \frac{F_{15} - F_{5}}{11} = \frac{610 - 5}{11} = \frac{605}{11} = 55$

$L = P$

Słownik

ciąg Fibonacciego

(F_{n})

zdefiniowany rekurencyjnie

ciąg Fibonacciego

(F_{n})

zdefiniowany rekurencyjnie

F_{n} = \{\begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n - 1} + F_{n - 2}, & n > 1 \end{cases}

3. Ciąg określony rekurencyjnie

M_R_W16_M1 Własności ciągów

4. Ciąg Fibonacciego

Słownik