Dãy Fibonacci

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 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à:

==Lịch sử==
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.

==Những bài toán mở đầu==
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.
===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:
- Cặp thỏ xám là cặp thỏ có độ tuổi 1 tháng.
- Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.

Nhìn vào hình vẽ trên ta nhận thấy:
- Tháng Giêng và tháng Hai: Chỉ có 1 đôi thỏ.
- Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có 2 đôi thỏ.
- Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có 3 đôi thỏ.
- Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có 2 + 3 = 5 đôi thỏ.
- Tháng Sáu: có ba đôi thỏ (2 đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có 3 + 5 = 8 đôi thỏ.

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ó:
- Với n = 1 ta được f(1) = 1.
- Với n = 2 ta được f(2) = 1.
- Với n = 3 ta được f(3) = 2.
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 đực===
Fibonacci đã 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:
- Nếu một trứng ong thụ tinh bởi chính con ong cái nó nở thành một con ong đực
- Tuy nhiên, nếu một trứng thụ tinh bởi một ong đực nó nở thành một con ong cái.
- Như vậy một con ong đực sẽ luôn có một mẹ, và một con ong cái sẽ có cả bố và mẹ.

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: 
- Trước một đời, thế hệ "n"-1: Con ong đực chỉ có một mẹ (1 ong cái).
- Trước hai đời, thế hệ "n"-2: Con ong cái đời "n-1" có 2 bố mẹ, một ong bố (đực) và một ong mẹ (cái)(2 con ong: 1 đực+ một cái)).
- Trước ba đời, thế hệ "n"-3: Con ong cái thế hệ "n"-2 lại có hai bố mẹ, một ong bố (đực) và một ong mẹ (cái), và con đực thế hệ "n"-2 có một mẹ (3 con ong: 1 ong đực + 2 ong cái)
- Trước bốn đời, thế hệ "n"-4: Hai con cái, mỗi con có 2 cha, mẹ và mỗi con đực có một mẹ (5 con ong: 2 ong đực 3 ong cái)
Tiếp tục quá trình này ta sẽ có một dãy số Fibonacci.

===Kết luận===
Như 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:
- f(0)= 0.
- f(1)= 1.
- f(2)= 1.
- f(n)= f(n-1) +f(n-2) với n > 2.
Đó là dãy Fibonacci và các số hạng trong dãy được gọi là các số Fibonacci.

==Các phần tử đầu tiên của dãy ==
Người ta chứng minh được rằng công thức tổng quát cho dãy Fibonacci là:

==Quan hệ với tỷ lệ vàng==
Tỷ lệ vàng formula_3 (phi), được định nghĩa như sau:

- Chia một đoạn thẳng có độ dài c thành hai đoạn có độ dài a và b, a > b
- Nếu a/b = c/a thì tỉ lệ này được gọi là tỷ lệ vàng.

Nếu quy độ dài đoạn nhỏ về đơn vị và độ dài đoạn lớn là x thì ta có a = x, b = 1, c = x+1, đẳng thức trong định nghĩa trở thành: 

nghiệm dương x của phương trình này chính là số formula_6.

===Công thức dạng tường minh===
Cũ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):

Như vậy, từ hệ thức truy hồi Fibonacci ta có:

sẽ dẫn tới phương trình xác định tỷ lệ vàng

(là phương trình đa thức đặ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 formula_11. Nhân hai vế với formula_12 có:

Chú ý rằng, theo định nghĩa formula_3 là một nghiệm của phương trình và nghiệm kia là formula_15. Do đó:

Bây giờ định nghĩa hàm:

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 formula_18 và formula_19. Tiếp tuc:

và

những chứng minh ở trên chứng tỏ rằng

Chú ý rằng, với hai giá trị khởi đầu bất kỳ của formula_23, hàm formula_24 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ếp===
Johannes Kepler, đã chứng minh sự hội tụ sau:

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 formula_27: 

vì thế, như dễ dàng thấy, formula_28 và như vậy formula_29

Chứng minh

==Phương pháp tính số==
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 a = ca+ ca +... +ca (1)

Khi đó nghiệm của hệ là r sẽ có dạng: r = cr + cr +cr +...+cr

Giải phương trình trên ta được các nghiệm phân biệt r,r...,r.Đồng thời ta có a=br +br +...+br (2)

Do vậy giải hệ phương trình (2) với a,a.., a cho trước ta sẽ nhận được các giá trị b,b...,b, 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)

== Biểu diễn ma trận ==
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à

có thể ký hiệu lại dưới dạng

từ điều này suy ra: formula_32. Các giá trị riêng của ma trận là formula_33 và formula_34 tương ứng với các vectơ riêng

và

Ta có vectơ của giá trị ban đầu có dạng

suy ra biểu thức số hạng thứ là

Từ đây ta có thể trực tiếp rút ra biểu thức dạng đóng cho số hạng thứ trong dãy Fibonacci:

Một cách tươ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 sử dụng phân tích riêng của nó, với formula_40 là ma trận đường chéo:

trong đó formula_42 và formula_43

Vì vậy biểu thức dạng đóng cho số hạng thứ của dãy Fibonacci được cho bởi phương trình:

thực hiện nhân ma trận, tiếp tục ta suy ra được công thức Binet

Ma trận 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:

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:

Lấy định thức cho hai vế của phương trình này, ta có được đẳng thức Cassini:

Hơn nữa, vì cho bất kỳ ma trận vuông , 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 bởi ),

cụ thể, với ,
Hai đẳng thức cuối cùng cho ta một cách tính đệ quy các số Fibonacci với phép toán số học trong thời gian , trong đó là thời gian để thực hiện phép nhân hai số có chữ số. Thời gian tính toán số hạng thứ 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ớ).

== Tổng các nghịch đảo ==
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 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ó.

==Tổng quát hóa==
===Mở rộng cho các số âm===
Dùng "F" = "F" - "F", 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" = -(-1)"F".

===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

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

Các số Lucas quan hệ với các số Fibonacci theo hệ thức

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:

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ố Tribonacci ====
Cá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 :

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 "x" − "x" − "x" − 1, xấp xỉ 1.83929, và cũng thoả mãn phương trình "x" + "x" = 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

ở đây cặp dấu ngoặc vuông ngoài là ký hiệu của hàm phần nguyên và

(Simon Plouffe, 1993). 

===Các tổng quát hóa khác===
Cá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ố "f" xác định theo đệ quy

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.

==Số nguyên tố Fibonacci==
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...

Các số nguyên tố Fibonacci với hàng nghìn chữ số đã được tìm thấy, song vẫn chưa biết liệu có vô số các số như vậy không.

"F" chia hết bởi "F", do đó, ngoại trừ "F" = 3, bất cứ số nguyên tố Fibonacci prime phải có chỉ số thứ tự cũng là số nguyên tố.

Không có số Fibonacci từ"F" = 8 trở đi mà lớn hơn hay nhỏ hơn một so với số nguyên tố.

Số Fibonacci duy nhất chính phương không tầm thường là số 144. Attila Pethő đã chứng minh trong 2001 chỉ có hữu hạn số lũy thừa hoàn hảo Fibonacci. Trong 2006, Y. Bugeaud, M. Mignotte, và S. Siksek đã chứng minh rằng chỉ duy nhất 8 và 144 là số lũy thừa hoàn hảo không tầm thường.

== Các xâu (ký tự) Fibonacci ==
Cho xâu Fibonacci được định nghĩa đệ quy như sau:

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à:

Độ 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.

==Số Fibonacci trong tự nhiên==
===Thực vật===
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.

==Xem thêm==
- Số đối-Fibonacci
- Số dẻo
- Số Padovan
- Số Perrin

==Tham khảo==
- Donald Knuth, "The Art of Computer Programming", third edition (1997)

==Liên kết ngoài==
- Hrant Arakelian, "Mathematics and History of the Golden Section". Logos (2014), 404 p. ISBN 978-5-98704-663-0, (rus.)

===Tiếng Anh===
- Alexey Stakhov, "Museum of Harmony and Golden Section ", (undated, 2005 or earlier).
- Subhash Kak, "The Golden Mean and the Physics of Aesthetics ", Archive of Physics, (2004).
- Ron Knott, "The Golden Section: Phi ", (2005).
- Ron Knott, "Representations of Integers using Fibonacci numbers ", (2004).
- Bob Johnson, "Fibonacci resources ", (2004)
- Donald E. Simanek, "Fibonacci Flim-Flam ", (undated, 2005 or earlier).
- Rachel Hall, "Hemachandra's application to Sanskrit poetry ", (undated; 2005 or earlier).
- Alex Vinokur, "Computing Fibonacci numbers on a Turing Machine ", (2003).
- (no author given), "Fibonacci Numbers Information ", (undated, 2005 or earlier).
- Wikisource, "", (2005).
- Fibonacci Numbers and the Golden Section - Ron Knott's Surrey University multimedia web site on the Fibonacci numbers, the Golden section and the Golden string.
- The Fibonacci Association incorporated in 1963, focuses on Fibonacci numbers and related mathematics, emphasizing new results, research proposals, challenging problems, and new proofs of old ideas.
- Dawson Merrill's Fib-Phi link page.
- Fibonacci primes