Dãy Fibonacci

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Dãy Fibonaccidãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 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à:


  F(n):=
  \left\{
   \begin{matrix}
    1\,,\qquad\qquad\qquad\quad\,\ \ \,&&\mbox{khi }n=1\,;\ \ \\
    1,\qquad\qquad\qquad\qquad\,&&\mbox{khi }n=2;\ \ \,\\
    F(n-1)+F(n-2)&&\mbox{khi }n>2.
   \end{matrix}
  \right.
Xếp các hình vuông có các cạnh là các số Fibonacci

Lịch sử[sửa | sửa mã nguồn]

Leonardo Fibonacci (1175 - 1250)

Dãy số Fibonacci rất đặc biệt này được Leonardo Fibonacci (hay còn có tên tên khác là Leonarda da Pisa) là 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 E 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 (người Pháp) 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.

Dãy số này hầu như biến hóa vô tận. Chính đều đó làm cho bao nhà toán học (chuyên nghiệp lẫn nghiệp dư) và ngay cả chúng ta say mê nghiên cứu, khám phá về nó.

Những bài toán mở đầu[sửa | sửa mã nguồn]

2 bài toán sau đây được trích từ sách Liber Abacci do Fibonacci ông 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ố mà chúng ta gọi là dãy Fibonacci.

Bài toán con thỏ[sửa | sửa mã nguồn]

"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?

GIA ĐÌNH NHÀ THỎ SAU 6 THÁNG

Trong hình vẽ trên, ta quy ước:

  • Cặp thỏ nâu 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 > 3 ta được: f(n) = f(n-1) + Số đôi thỏ ở tháng thứ 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[sửa | sửa mã nguồn]

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ẹ.
Số cụ tổ của 1 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:

  • 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 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[sửa | sửa mã nguồ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[sửa | sửa mã nguồn]

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

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

Quan hệ với tỷ lệ vàng[sửa | sửa mã nguồn]

Tỷ lệ vàng

Tỷ lệ vàng \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:

\frac{1}{x}=\frac{x}{1+x}, hay tương đương x^2-x-1=0,\,

chính là số \varphi = \frac{(1 + \sqrt{5})}{2}\approx 1.618\,033\,989.

Công thức dạng tường minh[sửa | sửa mã nguồn]

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

F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}, trong đó \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.\,

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

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 \begin{matrix}x^2=x+1,\end{matrix}\,. Nhân hai vế với x^{n-1}\, có:

x^{n+1} = x^n + x^{n-1}\,

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

\varphi^{n+1}    \,  = \varphi^n + \varphi^{n-1}\,
(1-\varphi)^{n+1}\,  = (1-\varphi)^n + (1-\varphi)^{n-1}\,

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

F_{a,b}(n) = a\varphi^n+b(1-\varphi)^n xác định với mọi số thực a,b\,

Tất cả các hàm này tthỏa mãn hệ thức truy hồi Fibonacci, thật vậy:

F_{a,b}(n+1)\,  = a\varphi^{n+1}+b(1-\varphi)^{n+1}
=a(\varphi^{n}+\varphi^{n-1})+b((1-\varphi)^{n}+(1-\varphi)^{n-1})
=a{\varphi^{n}+b(1-\varphi)^{n}}+a{\varphi^{n-1}+b(1-\varphi)^{n-1}}
=F_{a,b}(n)+F_{a,b}(n-1)\,

Bây giờ chọn a=1/\sqrt 5b=-1/\sqrt 5. Tiếp tuc:

F_{a,b}(0)=\frac{1}{\sqrt 5}-\frac{1}{\sqrt 5}=0\,\!

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)={{\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, hàm 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ếp[sửa | sửa mã nguồn]

Johannes Kepler, đã chứng minh sự hội tụ sau:

\frac{F(n+1)}{F(n)}\,hội tụ tới tỷ lệ vàng \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 \ne 0, b \ne 0:

\lim_{n\to\infty}\frac{F_{a,b}(n+1)}{F_{a,b}(n)} =\lim_{n\to\infty}\frac{a\varphi^{n+1}-b(1-\varphi)^{n+1}}{a\varphi^n-b(1-\varphi)^n}
=\lim_{n\to\infty}\frac{a\varphi-b(1-\varphi)(\frac{1-\varphi}{\varphi})^n}{a-b(\frac{1-\varphi}{\varphi})^n}
 = \varphi,

vì thế, như dễ dàng thấy, \left |{\frac{1-\varphi}{\varphi}}\right | < 1 và như vậy \lim_{n\to\infty}\left(\frac{1-\varphi}{\varphi}\right)^n=0

Chứng minh

Dạng ma trận[sửa | sửa mã nguồn]

(chưa có thông tin)

Phương pháp tính số[sửa | sửa mã nguồn]

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)

Trên đây chỉ là phương pháp giải Tổng Quát mà chưa nói rõ (chứng minh) về phương pháp giải, các bạn có thể tham khảo trong Giáo trình: Toán Rời Rạc của Nguyễn Đức Nghĩa - Nguyễn Tô Thành

Ứng dụng[sửa | sửa mã nguồn]

Các đẳng thức[sửa | sửa mã nguồn]

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

Chuỗi lũy thừa[sửa | sửa mã nguồn]

Tổng các nghịch đảo[sửa | sửa mã nguồn]

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 = \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ó.

Tổng quát hóa[sửa | sửa mã nguồn]

Mở rộng cho các số âm[sửa | sửa mã nguồ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ơ[sửa | sửa mã nguồn]

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ự[sửa | sửa mã nguồn]

Các số Lucas[sửa | sửa mã nguồn]

Đặ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

\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\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ố Tribonacci[sửa | sửa mã nguồn]

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 Bản mẫu: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, 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) = \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

a_{\pm} = \left(19 \pm 3 \sqrt{33}\right)^{1/3}
b = \left(586 + 102 \sqrt{33}\right)^{1/3}

(Simon Plouffe, 1993).[1]

Các tổng quát hóa khác[sửa | sửa mã nguồn]

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 nghiã 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 = \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.

 \sqrt[n]{|f_n|} \to 1.13198824\dots \mbox{ as } n \to \infty.

Số nguyên tố Fibonacci[sửa | sửa mã nguồn]

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.

Các xâu (ký tự) Fibonacci[sửa | sửa mã nguồn]

Tương tự với các biểu thức số, một xâu Fibonacci được định nghĩa đệ quy như sau:

 
  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. 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ố Fibonacci trong tự nhiên[sửa | sửa mã nguồn]

Thực vật[sửa | sửa mã nguồn]

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.

Hoa hướng dương có những nụ nhỏ kết thành những đường xoắn ốc

Các số Fibonacci cũng xuất hiện trong các bông 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 đường 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ỷ số vàng).

Hoa loa kèn có 3 cánh

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, hoa mao lương vàng có 5 cánh, hoa phi yến thường có 8 cánh, hoa vạn cúc 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ửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Tiếng Việt[sửa | sửa mã nguồn]

Tiếng Anh[sửa | sửa mã nguồn]