Dãy Fibonacci
Bách khoa toàn thư mở Wikipedia
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, 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à:
[sửa] Các phần tử đầu tiên của dãy
n | F(n) | n | F(n) | n | F(n) |
0 | 0 | 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 | 1.597 |
18 | 2.584 | 19 | 4.181 | 20 | 6.765 |
21 | 10.946 | 22 | 17.711 | 23 | 28.657 |
24 | 46.368 | 25 | 75.025 | 26 | 121.393 |
27 | 196.418 | 28 | 317.811 | 29 | 514.229 |
30 | 832.040 | 31 | 1.346.269 | 32 | 2.178.309 |
33 | 3.524.578 | 34 | 5.702.887 | 35 | 9.227.465 |
36 | 14.930.352 | 37 | 24.157.817 | 38 | 39.088.169 |
... | ... | ... | ... | ... | ... |
Người ta chứng minh được rằng công thức tổng quát cho dãy Fibonacci là:
[sửa] Lịch sử
[sửa] 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.
- 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+ 1 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 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 một ong cái)
Tiếp tục quá trình này ta sẽ có một dãy số Fibonacci.
[sửa] Quan hệ với tỷ lệ vàng
Tỷ lệ vàng (phi), được đinh nghĩa là tỷ số tỷ số khi chia đoạn thẳng thành hai phần sao cho tỷ lệ giữa đoạn lớn hơn với cả đoan ban đầu bằng tỷ số giữa đoạn nhỏ hơn và đoạn lớn. 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:
- , hay tương đương
chính là số .
[sửa] 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):
- , trong đó là tỷ lệ vàng ở trên.
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 dặc trưng của hồi quy).
Chứng minh (bằng quy nạp):
Một nghiệm bất lỳ của phương trình trên thoả mãn tính chất . Nhân hai vế với có:
Chú ý rằng, theo định nghĩa là một nghiệm của phương trình và nghiệm kia là . Do đó:
-
và
Bây giờ định nghĩa hàm:
- xác định với mọi số thực
Tất cả các hàm này tthỏa mãn hệ thức truy hồi Fibonacci, thật vậy:
Bây giờ chọn và . Tiếp tuc:
và
những chứng minh ở trên chứng tỏ rằng
- với mọi n.
Chú ý rằng, với hai giá trị khởi đầu bất kỳ của a,b, hàm là công thức tường minh cho một loạt các hệ thức truy hồi.
[sửa] Giới hạn của thương kế tiếp
Johannes Kepler, đã chứng minh sự hội tụ sau:
- hội tụ tới tỷ lệ vàng (phi)
Thực ra kết quả này đúng với mọi cặp giá trị khởi đầu, trừ (0, 0).
Chứng minh:
Từ công thức tường minh, ta có, với mọi :
-
,
vì thế, như dễ dàng thấy, và như vậy
[sửa] Dạng ma trận
[sửa] Phương pháp tính số
[sửa] Ứng dụng
[sửa] Số Fibonacci trong tự nhiên
[sửa] Các đẳng thức
- F(n + 1) = F(n) + F(n − 1)
- F(0) + F(1) + F(2) + ... + F(n) = F(n + 2) − 1
- F(1) + 2 F(2) + 3 F(3) + ... + n F(n) = n F(n + 2) − F(n + 3) + 2
[sửa] Chuỗi lũy thừa
[sửa] 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ó.
[sửa] Tổng quát hóa
[sửa] Mở rộng cho các số âm
Dùng Fn-2 = Fn - Fn-1, có thể mở rộng các số Fibonacci numbers 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.
[sửa] 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.
[sửa] Các dãy số nguyên tương tự
[sửa] Các số Lucas
Đặc biệt, dãy Fibonacci L với L(1) = 1 và L(2) = 3 được gọi là các 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:
- 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).
[sửa] 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 Tiêu bản:OEIS2C:
- 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ố (the ratio toward which adjacent tribonacci numbers tend). Nó là nghiệm của đa thức x3 − x2 − x − 1, approximately 1.83929, và ccũ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
ở đâ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).[1]
[sửa] 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 Fibonaccci.
Mộtdã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 nghiã dãy ngẫu nhiên Fibonacci sequence" là dãy các số fn xác định theo đệ quy
- f0 = 1, f1 = 1, and
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ứ nhội tụ về một hằng số khi n tăng vô hạn.
[sửa] Số nguyên tố Fibonacci
Một số các số Fibonacci cúng là các số nguyên tố như Tiêu bản:OEIS2C: 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.
[sửa] Các xâu (ký tự) Fibonacci
Tương tự với các biểu thức số, một xâu Fibonacci được định nghĩa đệ quy như sau:
- ,
trong đó dấu "+" ký hiệu cho phép ghép hai xâu. 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.
[sửa] Xem thêm
- Số đối-Fibonacci
- Số dẻo
- Số Padovan
- Số Perrin
[sửa] Tạp chí
- The Fibonacci Quarterly — an academic journal devoted to the study of Fibonacci numbers
[sửa] Tham khảo
- Donald Knuth, The Art of Computer Programming, third edition (1997)
[sửa] Liên kết ngoài
[sửa] Tiếng Việt
[sửa] 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, Table of first 1000 Fibonacci numbers, (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