Dãy Fibonacci là gì?

Dãy Fibonacci là gì?

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à: $$ F(n)=\begin{cases} 1& \text{khi }&n=1\\ 1& \text{khi }&n=2\\ F(n-1)+F(n-2)& \text{khi }&n>2 \end{cases}$$

Dãy số Fibonacci (Phibônaxi) đượ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.

Bài toán đếm số đôi 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

dãy số Fibonacci và bài toán đếm số con thỏ

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 > 2 ta có công thức tổng quát 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).

Công thức tổng quát của dãy 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}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)$$

Liên hệ với 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ỏ.

tỷ lệ vàng

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$. Nghiệm dương đó chính là $\varphi =\frac{1+\sqrt {5}{2}\approx 1.618\,033\,989$.

Bạn có thể đọc thêm tại wiki https://vi.wikipedia.org/wiki/D%C3%A3y_Fibonacci