Dãy Fibonacci là dãy số được xác định bằng công thức đệ qui: Show fn = fn-1 + fn-2, n ≥2, f0 = 1, f1 = 1 . Ví dụ: Bài toán con thỏ“Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi n tháng bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh?
 Trong hình vẽ trên, ta quy ước:
Nhìn vào hình vẽ trên ta nhận thấy:
… Khái quát, nếu n là số tự nhiên khác 0, gọi f(n) là số đôi thỏ có ở tháng thứ n, ta có:
Do đó với n > 3 ta được: f(n) = f(n-1) + f(n-2). Điều đó có thể được giải thích như sau: Các đôi thỏ sinh ra ở tháng n -1 không thể sinh con ở tháng thứ n, và ở tháng này đôi thỏ tháng thứ n – 2 sinh ra một đôi thỏ con nên số đôi thỏ được sinh ra ở tháng thứ n chính là giá trị của f(n – 2). Xét các trường hợp: Bài toán 1: Cho một số tự nhiên n (n<=40) bạn hãy lập trình tìm số Fibonaci thứ n? Ta thấy với n<=40 thì phương án đầu tiên ta cân nhắc đến đó chính là đệ quy: Nhìn vào công thức trên ta thấy ngay bản chất đệ quy, việc tính Fn ta có thể viết ngay rất dễ dàng và ngắn gọn: Function Fb(n:longint):int64; Begin If (n<=2) then exit(1) else fb:=fb(n-1) + fb(n-2); End; Ta sẽ nhận xét về cách làm này thông qua ví dụ sau: Khi ta gọi: x:=Fb(10) thì việc tính fb(10) này sẽ tính như sau: X:= fb(9) + fb(8) X:= fb(7) + fb(8) + fb(6) + fb(7) X:= fb(5) + fb(6) + fb(6) + fb(7) + fb(4) + fb(5) + fb(5) + fb(6) ….. Ta thấy ngay bước thứ 3: có rất nhiều lời gọi hàm trùng lặp nhau: f6 gọi 3 lần, f5 gọi 3 lần … chính điều này làm cho thời gian thực thi thuật toán này rất lớn. Chính vì vậy thuật toán đệ quy này chỉ chạy được với dữ liệu nhỏ. Với n>=44 thuật toán trên không khả thi. Bài toán 2: bạn hãy lập trình tìm số Fibonaci thứ n? (n<=1000.000) vì kết quả có thể rất lớn nên ta chỉ lấy kết quả là phần dư khi chia cho 1.000.000+7. * Ý tưởng 1: QHĐ O(n) để tìm số fibonaci thứ n Gọi F[i] là số Fibonaci thứ i. Khi đó ta thấy việc tính mảng F này rất nhanh chóng: Function Fibo(n:longint):int64; Var i:longint; Begin f[1]:=1; f[2]:=1; For i:=1 to n do f[i] : = (f[i-1] + f[i-2]) mod base; Exit(f[n]); End; * Ý tưởng 2: QHĐ O(n) để tìm số Fibonaci thứ n Ta nhận thấy để tính Fn thì chỉ cần quan tâm đến F[n-1] và f[n-2] vậy ta đã lãng phí bộ nhớ dành cho mảng F. Ý tưởng là ta sẽ dùng 3 biến fn, f1, f2: để lần lượt tính: Funtion Fibothu_n(n:longint):int64; Var f1,f2,k,i:int64; Begin if (n=1) or (n=2) then exit(1) else Begin f1:=1; f2:=1; fn:=f1+f2; i:=3; While i<n do Begin f1:=f2; f2:=fn; fn:=f1+f2; i:=i+1; End; Exit(fn) End; End;* Nhận xét: Ý tưởng 2 tốt hơn ý tưởng 1 rất nhiều về không gian bộ nhớ, tuy nhiên 2 ý tưởng này xét về độ phức tạp vẫn còn rất lớn: Sau đây ta xét bài toán thứ 3 như sau:Bài toán 3: Nguồn http://laptrinh.ntu.edu.vn/Problem/Details/1163 Xét dãy số Fibonaci {Fn} theo định nghĩa: F1 = F2 = 1 Fn = Fn – 1 + Fn – 2 với mọi n > 2 Cho n, hãy tính Fn và đưa ra số dư của Fn chia cho (1.000.000 + 7) Dữ liệu vào: n (0 < n ≤ 1000.000.000.000.000) Dữ liệu ra: một số nguyên – số dư tìm được Ta nhận thấy với n<=1000.000.000.000.000 thì 2 cách làm QHĐ với độ phức tạp O(n) không khả thi. Để giải quyết vấn đề này ta dùng phương pháp nhân ma trận. Phương án sau được đề xuất bởi Donald E. Knuth:
END.
Sử dụng 2 biến để lưu giá trị hiện tại của 2 số fibonaci. Mỗi lần sinh ra số fibonaci mới ta sẽ gán lại giá trị mới cho 2 biến này bằng đoạn code; F1:=F0+F1; F0:=F1-F0; program csc;uses crt;var n,i:integer; f0,f1:integer;begin clrscr; write('nhap so n:'); readln(n); f0:=0; f1:=1; for i:=2 to n do begin f1:=f0+f1; f0:=f1-f0; end; write('so fibonaci thu n la :',f1); readkey;end. Chương trình chạy tối đa đến N=23 với số fibonaci là 28657 . Nếu lên đến số 24 sẽ vượt quá phạm vi của biến kiểu integer. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là:
Leonardo Fibonacci (1175 - 1250) Một trang của Liber Abaci từ Thư viện Trung tâm Quốc gia (Florence) với dãy Fibonacci với vị trí trong chuỗi được mô tả bằng Số La Mã và giá trị bằng chữ số Ả Rập. Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đồ qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực. Henry Dudeney (1857 - 1930) (là một nhà văn và nhà toán học người Anh) nghiên cứu ở bò sữa, cũng đạt kết quả tương tự. Thế kỉ XIX, nhà toán học Edouard Lucas xuất bản một bộ sách bốn tập với chủ đề toán học giải trí, ông đã dùng tên Fibonacci để gọi dãy số kết quả của bài toán từ cuốn Liber Abaci – bài toán đã sinh ra dãy Fibonacci. 2 bài toán sau đây được trích từ sách Liber Abacci do Fibonacci viết vào năm 1202. Đây là những bài toán mẫu mực dẫn đến khảo sát dãy số Fibonacci. Mười ba ( F 7 ) cách sắp xếp các âm tiết dài và ngắn theo một nhịp độ dài sáu. Năm ( F 5 ) kết thúc bằng âm tiết dài và tám ( F 6 ) kết thúc bằng âm tiết ngắn. Bài toán số con thỏMột đôi thỏ (gồm một thỏ đực và một thỏ cái) không sinh cho đến khi chúng đủ 2 tháng tuổi. Sau khi đủ 2 tháng tuổi,mỗi đôi thỏ sinh một đôi thỏ con (gồm một thỏ đực và một thỏ cái) mỗi tháng. Hỏi sau n tháng có bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh
Trong hình vẽ trên, ta quy ước:
Nhìn vào hình vẽ trên ta nhận thấy:
Khái quát, nếu n là số tự nhiên khác 0, gọi f(n) là số đôi thỏ có ở tháng thứ n, ta có:
Do đó với n > 2 ta được: f(n) = f(n-1) + f(n-2). Điều đó có thể được giải thích như sau: Các đôi thỏ sinh ra ở tháng n -1 không thể sinh con ở tháng thứ n, và ở tháng này đôi thỏ tháng thứ n - 2 sinh ra một đôi thỏ con nên số đôi thỏ được sinh ra ở tháng thứ n chính là giá trị của f(n - 2). Số các "cụ tổ" của một con ong đựcFibonacci đã mô tả dãy các tổ tiên của một con ong đực như sau: (Loài ong có thể thụ tinh đơn tính hoặc lưỡng tính). Giả sử rằng:
Số cụ tổ của một con ong đực Ta bắt đầu tính số các con ong tổ tiên của một con ong đực. Xét một con ong đực ở thế hệ thứ n. Nhìn vào hình trên ta thấy:
Tiếp tục quá trình này ta sẽ có một dãy số Fibonacci. Kết luậnNhư vậy, công việc giải quyết hai bài toán trên của Fibonacci dẫn tới việc khảo sát dãy số f(n) xác định:
Đó là dãy Fibonacci và các số hạng trong dãy được gọi là các số Fibonacci.
Người ta chứng minh được rằng công thức tổng quát cho dãy Fibonacci là: F n = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left[{\Big (}{\frac {1+{\sqrt {5}}}{2}}{\Big )}^{n}-{\Big (}{\frac {1-{\sqrt {5}}}{2}}{\Big )}^{n}\right]}Tỷ lệ vàng Tỷ lệ vàng φ {\displaystyle \varphi } (phi), được đinh nghĩa là tỷ số khi chia đoạn thẳng thành hai phần sao cho tỷ lệ giữa cả đoạn ban đầu với đoạn lớn hơn bằng tỷ số giữa đoạn lớn và đoạn nhỏ. Có thể chứng minh rằng nếu quy độ dài đoạn lớn về đơn vị thì tỷ lệ này là nghiệm dương của phương trình: 1 x = x 1 + x {\displaystyle {\frac {1}{x}}={\frac {x}{1+x}}} , hay tương đương x 2 − x − 1 = 0 , {\displaystyle x^{2}-x-1=0,\,}chính là số φ = ( 1 + 5 ) 2 ≈ 1.618 033 989 {\displaystyle \varphi ={\frac {(1+{\sqrt {5}})}{2}}\approx 1.618\,033\,989} . Công thức dạng tường minhCũng như mọi dãy số xác định bởi công thức đệ quy tuyến tính, các số Fibonacci có thể tìm được công thức dạng tường minh. Ta sẽ chứng minh (công thức Binet): F ( n ) = φ n − ( 1 − φ ) n 5 {\displaystyle F\left(n\right)={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}} , trong đó φ {\displaystyle \varphi } là tỷ lệ vàng ở trên.Như vậy, từ hệ thức truy hồi Fibonacci ta có: F ( n + 2 ) − F ( n + 1 ) − F ( n ) = 0. {\displaystyle F(n+2)-F(n+1)-F(n)=0.\,}sẽ dẫn tới phương trình xác định tỷ lệ vàng x 2 − x − 1 = 0 , {\displaystyle x^{2}-x-1=0,\,}(là phương trình đa thức dặc trưng của hồi quy). Chứng minh Chứng minh (bằng quy nạp): Một nghiệm bất kỳ của phương trình trên thoả mãn tính chất x 2 = x + 1 , {\displaystyle {\begin{matrix}x^{2}=x+1,\end{matrix}}\,} . Nhân hai vế với x n − 1 {\displaystyle x^{n-1}\,} có: x n + 1 = x n + x n − 1 {\displaystyle x^{n+1}=x^{n}+x^{n-1}\,}Chú ý rằng, theo định nghĩa φ {\displaystyle \varphi } là một nghiệm của phương trình và nghiệm kia là 1 − φ {\displaystyle 1-\varphi } . Do đó:
Bây giờ định nghĩa hàm: F a , b ( n ) = a φ n + b ( 1 − φ ) n {\displaystyle F_{a,b}(n)=a\varphi ^{n}+b(1-\varphi )^{n}} xác định với mọi số thực a , b {\displaystyle a,b\,}Tất cả các hàm này thỏa mãn hệ thức truy hồi Fibonacci, thật vậy:
Bây giờ chọn a = 1 / 5 {\displaystyle a=1/{\sqrt {5}}} và b = − 1 / 5 {\displaystyle b=-1/{\sqrt {5}}} . Tiếp tuc: F a , b ( 0 ) = 1 5 − 1 5 = 0 {\displaystyle F_{a,b}(0)={\frac {1}{\sqrt {5}}}-{\frac {1}{\sqrt {5}}}=0\,\!}và F a , b ( 1 ) = φ 5 − ( 1 − φ ) 5 = − 1 + 2 φ 5 = − 1 + ( 1 + 5 ) 5 = 1 , {\displaystyle F_{a,b}(1)={\frac {\varphi }{\sqrt {5}}}-{\frac {(1-\varphi )}{\sqrt {5}}}={\frac {-1+2\varphi }{\sqrt {5}}}={\frac {-1+(1+{\sqrt {5}})}{\sqrt {5}}}=1,}những chứng minh ở trên chứng tỏ rằng F ( n ) = φ n − ( 1 − φ ) n 5 {\displaystyle F(n)={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}} với mọi n.Chú ý rằng, với hai giá trị khởi đầu bất kỳ của a , b {\displaystyle a,b} , hàm F a , b ( n ) {\displaystyle F_{a,b}(n)\,} là công thức tường minh cho một loạt các hệ thức truy hồi. Giới hạn của thương kế tiếpJohannes Kepler, đã chứng minh sự hội tụ sau: F ( n + 1 ) F ( n ) {\displaystyle {\frac {F(n+1)}{F(n)}}\,} hội tụ tới tỷ lệ vàng φ {\displaystyle \varphi } (phi)Thực ra kết quả này đúng với mọi cặp giá trị khởi đầu, trừ (0, 0). Từ công thức tường minh, ta có, với mọi a ≠ 0 , b ≠ 0 {\displaystyle a\neq 0,b\neq 0} :
vì thế, như dễ dàng thấy, | 1 − φ φ | < 1 {\displaystyle \left|{\frac {1-\varphi }{\varphi }}\right|<1} và như vậy lim n → ∞ ( 1 − φ φ ) n = 0 {\displaystyle \lim _{n\to \infty }\left({\frac {1-\varphi }{\varphi }}\right)^{n}=0} Chứng minh Việc giải một hệ thức truy hồi tổng quát dựa trên việc giải phương trình đặc trưng của nó. Lấy ví dụ như, cho hệ thức truy hồi dạng an = c1an-1+ c2an-2 +... +ckan-k (1) Khi đó nghiệm của hệ là r sẽ có dạng: rn = c1rn-1 + c2rn-2 +c3rn-3 +...+ckrn-k Giải phương trình trên ta được các nghiệm phân biệt r1,r2,....,rn-1.Đồng thời ta có an=b1r1n +b2r2n +...+bn-1rn-1n (2) Do vậy giải hệ phương trình (2) với a1,a2,.., an cho trước ta sẽ nhận được các giá trị b1,b2,...,bn-1, thay trở lại ta sẽ có phương trình tổng quát dành cho hệ thức truy hồi (1) Từ hệ thức truy hồi ta có phương trình liên hệ lặp tuyến tính 2 chiều mô tả dãy Fibonacci là ( F k + 2 F k + 1 ) = ( 1 1 1 0 ) ( F k + 1 F k ) {\displaystyle {F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}}có thể ký hiệu lại dưới dạng F → k + 1 = A F → k , {\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}từ điều này suy ra: F → n = A n F → 0 {\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}} . Các giá trị riêng của ma trận A là φ = 1 2 ( 1 + 5 ) {\displaystyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})} và − φ − 1 = 1 2 ( 1 − 5 ) {\displaystyle -\varphi ^{-1}={\frac {1}{2}}(1-{\sqrt {5}})} tương ứng với các vectơ riêng μ → = ( φ 1 ) {\displaystyle {\vec {\mu }}={\varphi \choose 1}}và ν → = ( − φ − 1 1 ) . {\displaystyle {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}Ta có vectơ của giá trị ban đầu có dạng F → 0 = ( 1 0 ) = 1 5 μ → − 1 5 ν → , {\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}suy ra biểu thức số hạng thứ n là F → n = 1 5 A n μ → − 1 5 A n ν → = 1 5 φ n μ → − 1 5 ( − φ ) − n ν → = 1 5 ( 1 + 5 2 ) n ( φ 1 ) − 1 5 ( 1 − 5 2 ) n ( − φ − 1 1 ) , {\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}~\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}{\varphi \choose 1}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}{-\varphi ^{-1} \choose 1},\end{aligned}}}Từ đây ta có thể trực tiếp rút ra biểu thức dạng đóng cho số hạng thứ n trong dãy Fibonacci: F n = 1 5 ( 1 + 5 2 ) n − 1 5 ( 1 − 5 2 ) n . {\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}.}Một cách tuơng đương, ta có thể tính toán ma trận lũy thừa bằng cách chéo hóa ma trận A sử dụng phân tích riêng của nó, với Λ {\displaystyle \Lambda } là ma trận đường chéo: A = S Λ S − 1 , A n = S Λ n S − 1 , {\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}trong đó Λ = ( φ 0 0 − φ − 1 ) {\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\end{pmatrix}}} và S = ( φ − φ − 1 1 1 ) . {\displaystyle S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.} Vì vậy biểu thức dạng đóng cho số hạng thứ n của dãy Fibonacci được cho bởi phương trình: ( F n + 1 F n ) = A n ( F 1 F 0 ) = S Λ n S − 1 ( F 1 F 0 ) = S ( φ n 0 0 ( − φ ) − n ) S − 1 ( F 1 F 0 ) = ( φ − φ − 1 1 1 ) ( φ n 0 0 ( − φ ) − n ) 1 5 ( 1 φ − 1 − 1 φ ) ( 1 0 ) , {\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}thực hiện nhân ma trận, tiếp tục ta suy ra được công thức Binet F n = φ n − ( − φ ) − n 5 . {\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}Ma trận A có định thức là −1, và vì thế nó là một ma trận 2×2 đơn môđun (unimodular). Một ma trận đơn môđun là ma trận vuông có định thức là 1 hoặc −1. Tính chất này có thể được hiểu theo cách biểu diễn liên phân số cho tỉ lệ vàng: φ = 1 + 1 1 + 1 1 + 1 1 + ⋱ . {\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}Các số Fibonacci chính là tỉ số giữa hai giản phân liên tiếp của liên phân số cho φ, mà ma trận được tạo ra từ các giản phân liên tiếp của một phân số liên tục bất kỳ thì có định thức là +1 hoặc −1, vậy nó là ma trận đơn môđun. Ta có biểu diễn ma trận đưa ra biểu thức dạng đóng sau đây cho các số Fibonacci: ( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) . {\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}Lấy định thức cho hai vế của phuơng trình này, ta có được đẳng thức Cassini: ( − 1 ) n = F n + 1 F n − 1 − F n 2 . {\textstyle (-1)^{n}=F_{n+1}F_{n-1}-F_{n}^{2}.}Hơn nữa, vì An Am = An+m cho bất kỳ ma trận vuông A, có thể suy ra các đẳng thức bên dưới (chúng được rút ra từ hai hệ số khác nhau của ma trận tích, dễ dàng suy ra đẳng thức thứ hai từ cái đầu tiên bằng cách thay n bởi n + 1), F m F n + F m − 1 F n − 1 = F m + n − 1 , F m F n + 1 + F m − 1 F n = F m + n . {\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}cụ thể, với m = n, F 2 n − 1 = F n 2 + F n − 1 2 F 2 n = ( F n − 1 + F n + 1 ) F n = ( 2 F n − 1 + F n ) F n . {\displaystyle {\begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\\&=(2F_{n-1}+F_{n})F_{n}.\end{aligned}}}Hai đẳng thức cuối cùng cho ta một cách tính đệ quy các số Fibonacci với O(log(n)) phép toán số học trong thời gian O(M(n) log(n)), trong đó M(n) là thời gian để thực hiện phép nhân hai số có n chữ số. Thời gian tính toán số hạng thứ n của dãy Fibonacci sử dụng công thức này tương tự như cách tính với biểu thức ma trận dạng đóng, nhưng với ít hơn các bước không cần thiết nếu cần phải tránh thực hiện việc tính toán lại một số Fibonacci đã được tính ra trước đó (đệ quy có nhớ).[1]
Tổng vô hạn các nghịch đảo của các số Fibonacci có tính chất tương tự các hàm theta. Giá trị mang tên hằng số nghịch đảo Fibonacci C = ∑ k = 1 ∞ 1 F k = 3.359885 … {\displaystyle C=\sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=3.359885\dots }đã được chứng minh là số vô tỷ bởi Richard André-Jeannin, nhưng chưa biết một biểu thức dạng chính xác của nó. Dùng Fn-2 = Fn - Fn-1, có thể mở rộng các số Fibonacci cho các chỉ số nguyên âm. Khi đó ta có:... -8, -5, -3, -2, -1, 1, 0, 1, 1, 2, 3, 5, 8,... và F-n = -(-1)nFn. Không gian vectơThuật ngữ dãy Fibonacci cũng được dùng cho các hàm g từ tập các số nguyên tới một trường F thoả mãn g(n+2) = g(n) + g(n+1). Các hàm này có thể biểu diễn dưới dạng g(n) = F(n)g(1) + F(n-1)g(0),do vậy các dãy Fibonacci hình thành một không gian vectơ với hàm F(n) và F(n-1) là một cơ sở. Tổng quát hơn, giá trị của g có thể lấy trong một nhóm abel (xem như một z-module). Khi đó dãy Fibonacci là một Z-module 2 chiều. Các dãy số nguyên tương tựCác số LucasĐặc biệt, dãy Fibonacci L với L(1) = 1 và L(2) = 3 được gọi là số Lucas, theo tên của Edouard Lucas. Dãy Lucas đã được Leonhard Euler đề cập đến năm 1748, trong Nhập môn giải tích vô hạn (Introductio in Analysin Infinitorum). Về ý nghĩa, các sô Lucas L(n) là luỹ thừa bậc n của tỷ lệ vàng ( 1 2 ( 1 + 5 ) ) n = 1 2 ( L ( n ) + F ( n ) 5 ) . {\displaystyle \left({\frac {1}{2}}\left(1+{\sqrt {5}}\right)\right)^{n}={\frac {1}{2}}\left(L(n)+F(n){\sqrt {5}}\right).}Các số Lucas quan hệ với các số Fibonacci theo hệ thức L ( n ) = F ( n − 1 ) + F ( n + 1 ) . {\displaystyle L\left(n\right)=F\left(n-1\right)+F\left(n+1\right).\,}Một tổng quát hoá của dãy Fibonacci là các dãy Lucas. Nó có thể định nghĩa như sau: U(0) = 0 U(1) = 1 U(n + 2) = PU(n + 1) − QU(n)trong đó dãy Fibonacci là trường hợp đặc biệt khi P = 1 và Q = −1. Một dạng khác của các dãy Lucas bắt đầu với V(0) = 2, V(1) = P. Các dãy này có ứng dụng trong lý thuyết số để kiểm tra tính nguyên tố. Các dãy Padovan là tương tự với hệ thức truy hồi P(n) = P(n − 2) + P(n − 3). Các số TribonacciCác số tribonacci tương tự các số Fibonacci, nhưng thay vì khởi động với hai phần tử, dãy này khởi động với ba phân tử và mỗi số tiếp theo bằng tổng của ba phần tử đứng trước. Sau đây là một số sô tribonacci A000073: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …Giá trị của hằng số tribonacci là tỷ số (tỷ lệ mà các số tribonacci liền kề có xu hướng). Nó là nghiệm của đa thức x3 − x2 − x − 1, xấp xỉ 1.83929, và cũng thoả mãn phương trình x + x−3 = 2. Nó có vai trò quan trọng khi nghiên cứu khối snub. Các số tribonacci cũng được cho bởi T ( n ) = [ 3 b ( 1 3 ( a + + a − + 1 ) ) n b 2 − 2 b + 4 ] {\displaystyle T(n)=\left[3\,b{\frac {\left({\frac {1}{3}}\left(a_{+}+a_{-}+1\right)\right)^{n}}{b^{2}-2b+4}}\right]}ở đây cặp dấu ngoặc vuông ngoài là ký hiệu của hàm phần nguyên và a ± = ( 19 ± 3 33 ) 1 / 3 {\displaystyle a_{\pm }=\left(19\pm 3{\sqrt {33}}\right)^{1/3}} b = ( 586 + 102 33 ) 1 / 3 {\displaystyle b=\left(586+102{\sqrt {33}}\right)^{1/3}}(Simon Plouffe, 1993).[1] Lưu trữ 2006-04-05 tại Wayback Machine Các tổng quát hóa khácCác đa thức Fibonacci là một tổng quát hoá khác của dãy Fibonacci. Một dãy Fibonacci ngẫu nhiên có thể xác định bằng việc ném đồng xu cho mỗi n trong dãy và lấy F(n)=F(n−1)+F(n−2) nếu đồng xu sấp và lấy F(n)=F(n−1)−F(n−2) nếu đồng xu ngửa. Có thể định nghĩa dãy "ngẫu nhiên Fibonacci" là dãy các số fn xác định theo đệ quy f0 = 1, f1 = 1, and f n = { f n − 1 + f n − 2 , with probability 0.5 f n − 1 − f n − 2 , with probability 0.5 {\displaystyle f_{n}=\left\{{\begin{matrix}f_{n-1}+f_{n-2},&{\mbox{with probability 0.5}}\\f_{n-1}-f_{n-2},&{\mbox{with probability 0.5}}\end{matrix}}\right.}Hầu chắc chắn rằng căn bậc n của trị tuyệt đối của số hạng thứ n hội tụ về một hằng số khi n tăng vô hạn. | f n | n → 1.13198824 … as n → ∞ . {\displaystyle {\sqrt[{n}]{|f_{n}|}}\to 1.13198824\dots {\mbox{ as }}n\to \infty .}Một số các số Fibonacci cũng là các số nguyên tố như: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229,…. Chưa biết chắc rằng có vô hạn số nguyên tố Fibonacci không. Cho xâu Fibonacci được định nghĩa đệ quy như sau: F n := F ( n ) := { b khi n = 0 ; a khi n = 1 ; F ( n − 1 ) + F ( n − 2 ) khi n > 1. {\displaystyle F_{n}:=F(n):={\begin{cases}b&{\mbox{khi }}n=0;\\a&{\mbox{khi }}n=1;\\F(n-1)+F(n-2)&{\mbox{khi }}n>1.\\\end{cases}}} ,trong đó dấu "+" ký hiệu cho phép ghép hai xâu. Hãy viết giải thuật (đệ quy hoặc phi đệ quy) tính độ dài xâu. Hãy cho biết giá trị của chuỗi với n = 7 Dãy các xâu Fibonacci khởi đầu là: b, a, ab, aba, abaab, abaababa, abaababaabaab, …Độ dài của mỗi xâu Fibonacci chính là số Fibonacci, và có một xâu Fibonacci tương ứng với mỗi số Fibonacci. Các xâu Fibonacci cung cấp dữ liệu vào cho các minh dụ cho một vài thuật toán máy tính. Dãy Fibonacci xuất hiện ở khắp nơi trong thiên nhiên. Những chiếc lá trên một nhành cây mọc cách nhau những khoảng tương ứng với dãy số Fibonacci. Các số Fibonacci xuất hiện trong những bông hoa. Hầu hết các bông hoa có số cánh hoa là một trong các số: 3, 5, 8, 13, 21, 34, 55 hoặc 89. Hoa loa kèn có 3 cánh, Họ Mao lương có 5 cánh, phi yến thường có 8 cánh, hoa cúc vạn thọ có 13 cánh, hoa cúc tây có 21 cánh, hoa cúc thường có 34, hoặc 55 hoặc 89 cánh. Nếu quan sát các 'mắt' trên vỏ của một trái thơm già, bạn có thể may mắn tìm thấy được số mắt trên 2 đường vòng cung chéo trên vỏ trái thơm là 2 số Fibonacci nào đó, thí dụ 13 và 21. Các số Fibonacci trong hoa hướng dương. Những nụ nhỏ sẽ kết thành hạt ở đầu bông hoa hướng dương được xếp thành hai tập các hình xoắn ốc: một tập cuộn theo chiều kim đồng hồ, còn tập kia cuộn ngược theo chiều kim đồng hồ. Số các đường xoắn ốc hướng thuận chiều kim đồng hồ thường là 34 còn ngược chiều kim đồng hồ là 55. Đôi khi các số này là 55 và 89, và thậm chí là 89 và 144. Tất cả các số này đều là các số Fibonacci kết tiếp nhau (tỷ số của chúng tiến tới Tỷ lệ vàng) Đầu hoa cúc vạn thọ thể hiện sự sắp xếp theo xoắn ốc 21 (xanh lam) và 13 (xanh dương). Hình minh họa mô hình Vogel cho n = 1 ... 500 Hoa loa kèn có 3 cánh
|
