Ciąg Fibonacciego

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:

Początkowe wartości ciągu to:

n	F(n)
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55
11	89
12	144
13	233
14	377
15	610
16	987
17	1597
18	2584
19	4181
20	6765
21	10946
22	17711
23	28657
24	46368
25	75025
26	121393
27	196418
28	317811
29	514229
30	832040
31	1346269
32	2178309
33	3524578
34	5702887
35	9227465
36	14930352
37	24157817
38	39088169
39	63245986
40	102334155
41	165580141
42	267914296
43	433494437
44	701408733
45	1134903170
46	1836311903
47	2971215073
48	4807526976
49	7778742049
50	12586269025
51	20365011074
52	32951280099
53	53316291173
54	86267571272
55	139583862445
56	225851433717
57	365435296162
58	591286729879
59	956722026041
60	1548008755920
61	2504730781961
62	4052739537881
63	6557470319842
64	10610209857723
65	17167680177565
66	27777890035288
67	44945570212853
68	72723460248141
69	117669030460994
70	190392490709135
71	308061521170129
72	498454011879264
73	806515533049393
74	1304969544928657
75	2111485077978050
76	3416454622906707
77	5527939700884757
78	8944394323791464
79	14472334024676221
80	23416728348467685
81	37889062373143906
82	61305790721611591
83	99194853094755497
84	160500643816367088
85	259695496911122585
86	420196140727489673
87	679891637638612258
88	1100087778366101931
89	1779979416004714189
90	2880067194370816120

$F_n := F(n):= \begin{cases} 0 & \mbox{dla } n = 0; \\ 1 & \mbox{dla } n = 1; \\ F(n-1)+F(n-2) & \mbox{dla } n > 1. \\ \end{cases}$

Kolejne wyrazy tego ciągu nazywamy liczbami Fibonacciego.

Spis treści

1 Wzór Bineta
2 Własności
3 Obliczanie liczb Fibonacciego
4 Graficzna reprezentacja dwójkowa
5 Złota liczba
6 Ciąg Lucasa
7 Liczby pierwsze w ciągu Fibonacciego
8 Kod w języku Pascal/Delphi na obliczanie n-tej liczby ciagu F.
9 Uogólnienie ciągu Fibonacciego
- 9.1 ciąg 'Tribonacciego'
- 9.2 ciąg 'Tetranacciego'
10 Zobacz też
11 Linki zewnętrzne

[edytuj] Wzór Bineta

Jawny wzór na n-ty wyraz ciągu Fibonacciego możemy otrzymać np. korzystając z metody funkcji tworzących.

Zdefiniujmy ciąg $f_n := F_{n+1}\,$ i dla tego ciągu $f n$ obliczmy wzór na jego n-ty wyraz.

Funkcja tworząca dla tego ciągu ma postać

$s(x)=\sum_{n=0}^\infty f_n x^n$

Podstawiając $f_n = f_{n-1} + f_{n-2}\,$ otrzymujemy:

$s(x)= 1 + x + \sum_{n=2}^{\infty} \left( f_{n-2} + f_{n-1} \right) x^n$

$= 1 + x + x^2 \sum_{n=2}^\infty f_{n-2} x^{n-2} + x \sum_{n=2}^\infty f_{n-1} x^{n-1}$

$= 1 + x + x^2 s(x) + x (s(x)-1) = 1 + x s(x) + x^2 s(x)\,$

tak więc: $s(x) = \frac{1}{1 - x - x^2}$ Wyrażenie $\frac{1}{1 - x - x^2}$ możemy przedstawić w prostszej postaci, a mianowicie: $\frac{1}{1 - x - x^2} = A/(1-ax) + B/(1-bx)$

gdzie $a={1 + \sqrt{5} \over 2}$ $b={1 - \sqrt{5} \over 2}$ $A={a \over a-b}$ $B={-b \over a-b}$

wówczas $s(x)=A \sum_{n=0}^\infty a^n x^n + B \sum_{n=0}^\infty b^n x^n = \sum_{n=0}^\infty {(a^{n+1} - b^{n+1}) \over (a-b)}x^n$ tak więc $f_n = {(a^{n+1} - b^{n+1}) \over (a-b)}$

Podstawiając $F_n=f_{n-1}\,$ otrzymujemy ostatecznie tzw. wzór Bineta :

$F_n = \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n - \frac{1}{\sqrt 5}\left(\frac{1 - \sqrt 5}{2}\right)^n$

Ponieważ drugi człon tego wyrażenia szybko zbiega do zera

$F_n \approx \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n$

[edytuj] Własności

Można też wyrazić wartości kolejnych elementów ciągu za pomocą symbolu Newtona :

$F_n = \sum_{k=1}^n{n-k \choose k-1}$

Zachodzą równości:

$\sum_{k=1}^n F_k = F_{n+2}-1$

$\sum_{i=0}^n iF_i = nF_{n+2} - F_{n+3} + 2$

$\sum_{k=1}^n F_k^2 = F_{n+1}F_n$ (równanie ilustruje rysunek)

$\sum_{k=1}^n F_k^3 = (F_{3n+2}+ (-1)^{n+1}6 F_{n-1}+5 )/10$

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

$F_{2n-1} = {F_n}^2 + {F_{n-1}}^2$

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

$F_{n+1}F_{m} + F_n F_{m-1} = F_{m+n}\,$

Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:

Z wyjątkiem jednocyfrowych liczb Fibonacciego (liczb występujących w ciągu Fibonacciego), zawsze cztery albo pięć następujących po sobie wyrazów ciągu ma tę samą liczbę cyfr w układzie dziesiętnym.
Jedynymi liczbami w całym ciągu Fibonacciego, będącymi kwadratami liczb całkowitych są 1 i 144.
Największy wspólny dzielnik dwóch dowolnych liczb Fibonacciego jest liczbą Fibonacciego, której numer jest równy najmniejszemu wspólnemu dzielnikowi tych liczb.
Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.

[edytuj] Obliczanie liczb Fibonacciego

Teoretycznie wartości kolejnych wyrazów ciągu Fibonacciego mogą być obliczone wprost z definicji, jest to jednak metoda na tyle wolna, że stosowanie jej ma tylko sens dla niewielu początkowych wyrazów ciągu, nawet na bardzo szybkich komputerach. Wynika to z tego, że definicja $F n$ wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. Drzewo wywołań takiego algorytmu dla parametru $n$ musi mieć co najmniej $F n$ liści o wartości 1. Ponieważ ciąg Fibonacciego rośnie wykładniczo, oznacza to wyjątkowo słabą wydajność.

Istnieje równie prosta i znacznie szybsza metoda. Obliczamy wartości ciągu po kolei: F₀, F₁, F₂ i tak aż do F_n, za każdym razem korzystając z tego, co już obliczyliśmy. Nie musimy nawet zapamiętywać wszystkich obliczonych dotychczas wartości – ponieważ wystarczą dwie ostatnie. Daje to złożoność liniową – o wiele lepszą od wykładniczej złożoności poprzedniej metody. Metoda ta może być postrzegana jako zastosowanie programowania dynamicznego.

 FIBONACCI

Można zrobić to jeszcze szybciej. Łatwo zauważyć, że zachodzi zależność:

$\begin{bmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} =\begin{bmatrix} F_{n+3} & F_{n+2} \\ F_{n+2} & F_{n+1} \end{bmatrix}$

Ponieważ równocześnie:

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} =\begin{bmatrix} F_2 & F_1 \\ F_1 & F_0 \end{bmatrix}$

to indukcyjnie:

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix},\quad n\ge 1$

A ponieważ istnieją bardzo wydajne algorytmy potęgowania macierzy, możemy wyliczyć dowolny wyraz ciągu Fibonacciego za pomocą logarytmicznej ilości mnożeń. Stanowi to ogromny kontrast wobec wykładniczej ilości (co prawda szybszych) dodawań najbardziej naiwnej metody.

[edytuj] Graficzna reprezentacja dwójkowa

Ciąg Fibonacciego w systemie dwójkowym

Jeśli kolejne wyrazy ciągu zapisać w systemie dwójkowym, jeden pod drugim, z wyrównaniem do prawej strony to otrzymamy wydłużający się w dół trójkąt, którego elementy powtarzają sie ("czubek" pojawia się poniżej, przy prawej krawędzi, w coraz dłuższym rozwinięciu - pojawia się nad nim "biały trójkąt"), co czyni go podobnym do fraktala. Dla lepszej przejrzystości na rysunku obok wszystkie zera zastąpiono białymi punktami, a jedynki - czarnymi.

[edytuj] Złota liczba

granica ciągu

$\frac{F(n+1)}{F(n)}$

czyli ilorazów sąsiadujących ze sobą wyrazów ciągu Fibonacciego to tzw. złota liczba lub złota proporcja definiowana jako dodatnie rozwiązanie równania :

$\frac{x}{1}=\frac{1}{x-1}$ lub równoważnego $x=1+\frac{1}{x}$

Dowód (zakładający istnienie takiej granicy):

$x={\lim_{n\to\infty}\frac{F(n+1)}{F(n)}}$

$=\lim_{n\to\infty}\frac{F(n)+F(n-1)}{F(n)}$

$=\lim_{n\to\infty}\left(\frac{F(n)}{F(n)}+\frac{F(n-1)}{F(n)}\right)$

$=1+\lim_{n\to\infty}\frac{F(n-1)}{F(n)}$

$=1+\frac{1}{\displaystyle\lim_{n\to\infty}\frac{F(n)}{F(n-1)}}$

$=1+\frac1x$

Jest ona także pierwiastkiem wielomianu x² − x − 1 oraz równania x + x⁻² = 2

Zauważmy, że w powyższym dowodzie informacja o początkowych wyrazach ciągu czy też jakichkolwiek innych nie była wykorzystywana. Przeto dla dowolnego ciągu

$G_n := G(n):= \begin{cases} a & \mbox{dla } n = 0; \\ b & \mbox{dla } n = 1; \\ G(n-1)+G(n-2) & \mbox{dla } n > 1. \\ \end{cases}$

zachodzi wzór : $G_n = a*F_{n-1} + b*F_n\,$ Czasem taki ciąg G również nazywany jest ciągiem Fibonacciego lub ciągiem uogólnionym. Jeżeli a i b nie są równocześnie zerami to granica zbieżności ciągu : $\frac{G(n+1)}{G(n)}$ jest taka sama jak dla 'oryginalnego' ciągu Fibonacciego.

Kolejne wyrazy ciągu : $\frac{F(n+1)}{F(n)}$ są także wartością n-tego odcinka ułamka łańcuchowego : $\varphi = [1; 1, 1, 1, ...] = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}}$

wartościami kolejnych 'odcinków' są liczby :

$\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1}}}}$

[edytuj] Ciąg Lucasa

Ciąg Lucasa jest pewną odmianą ciągu Fibonacciego, definiujemy go

$L_n := L(n):= \begin{cases} 2 & \mbox{dla } n = 0; \\ 1 & \mbox{dla } n = 1; \\ L(n-1)+L(n-2) & \mbox{dla } n > 1. \\ \end{cases}$

Zachodzą równości:

$L_n=F_{n-1}+F_{n+1}\,$

$F_n = \begin{matrix}\frac{1}{5}\end{matrix}(L_{n-1}+L_{n+1})$ .

$F_{n+1} = \begin{matrix}\frac{1}{2}\end{matrix}(F_n+L_n)$ .

$F_{2n} = F_n L_n\,$ .

$F_{m+n} = \begin{matrix}\frac{1}{2}\end{matrix}(F_m L_n + F_n L_m)$ .

$F_{m-n} = \begin{matrix}\frac{1}{2}\end{matrix}(-1)^n(F_m L_n - F_n L_m)$ .

[edytuj] Liczby pierwsze w ciągu Fibonacciego

Kilka początkowych wyrazów w ciągu Fibonacciego to także liczby pierwsze A005478 a mianowicie: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229.. Wydaje się prawdopodobne, że liczb pierwszych w ciągu Fibonacciego istnieje nieskończenie wiele, lecz problem ten jak dotąd nie doczekał się rozstrzygnięcia.

[edytuj] Kod w języku Pascal/Delphi na obliczanie n-tej liczby ciagu F.

program ciag_fib;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
i,n:integer;
s,a,b:real;
begin
writeln('Podaj liczbe ciagu Fibonacciego: ');
readln(n);
a:=1;
b:=1;
for i:=1 to n do
begin
a:=a*((1+sqrt(5))/2);
b:=b*((1-sqrt(5))/2);
end;
s:=(1/sqrt(5))*a-(1/sqrt(5))*b;
writeln(s:2:0);
readln;
end.

[edytuj] Uogólnienie ciągu Fibonacciego

[edytuj] ciąg 'Tribonacciego'

Różni się od ciągu Fibonacciego tym, że każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich trzech wyrazów zamiast dwóch. Jego kilka początkowych wyrazów to: A000073 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890.. Stała 'Tribonacciego' jest granicą ciągu : $\frac{T(n+1)}{T(n)}$ (gdzie $T (n)$ jest n-tym wyrazem ciągu 'Tribonacciego') czyli analogiem złotej liczby dla ciągu Fibonacciego. Jest ona pierwiastkiem wielomianu x³ − x² − x − 1 oraz równania x + x⁻³ = 2 i wynosi ok. 1.83929.

[edytuj] ciąg 'Tetranacciego'

Różni się od ciągu Fibonacciego tym, każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich czterech wyrazów zamiast dwóch. Jego kilka początkowych wyrazów to: A000078 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569.. Stała 'Tetranacciego' jest granicą ciągu : $\frac{T(n+1)}{T(n)}$ (gdzie $T (n)$ jest n-tym wyrazem ciągu 'Tetranacciego'). Jest ona pierwiastkiem wielomianu x⁴ − x³ − x² − x − 1 oraz równania x + x⁻⁴ = 2 i wynosi ok. 1.92756.

tutaj można znaleźć pierwsze trzysta elementów ciągu Fibonacciego tablica ciągu Fibonacciego

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Źródło: "http://pl.wikipedia.org../../../c/i/%C4%85/Ci%C4%85g_Fibonacciego_47d0.html"

Kategoria: Teoria liczb

We provide Linux to the World