Dãy số Fibonacci và bài toán con thỏ

I. Dãy Fibonaci

Dãy số Fibonaci được xác định bởi công thức sau:

${\begin{cases} f_{0} = 0. \\ f_{1} = 1. \\ f_{i} = f_{i - 1} + f_{i - 2}, & với i \geq 2. \end{cases}$

Một số phần tử đầu tiên của dãy Fibonaci là: $0, 1, 1, 2, 3, 5, 8$ Ngoài ra, số Fibonaci thứ $N$ còn có thể tính bằng công thức tổng quát:

$f_{N} = \frac{1}{\sqrt{5}} \times [{(\frac{1 + \sqrt{5}}{2})}^{N} - {(\frac{1 - \sqrt{5}}{2})}^{N}] (1)$

Dãy Fibonaci là đáp án của một số bài toán dưới đây:

Phát biểu bài toán:

Ban đầu chỉ có một cặp thỏ được sinh ra.
Hai tháng sau khi ra đời, mỗi cặp thỏ sẽ sinh ra một cặp thỏ con mới.
Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo, chúng lại sinh được một cặp con mới.
Giả sử các con thỏ không bao giờ chết, hãy đếm số lượng cặp thỏ ở tháng thứ $N ?$

Ví dụ: Với $N = 5,$ ta thấy:

Giải thích:

Giữa tháng thứ nhất: $1$ cặp (cặp ban đầu).
Giữa tháng thứ hai: $1$ cặp (cặp ban đầu vẫn chưa đẻ).
Giữa tháng thứ ba: $2$ cặp (cặp ban đầu đẻ thêm một cặp con).
Giữa tháng thứ tư: $3$ cặp (cặp ban đầu tiếp tục đẻ).
Giữa tháng thứ năm: $5$ cặp (cặp ban đầu tiếp tục đẻ và cặp thứ hai bắt đầu đẻ).