Hằng đẳng thức về dãy số Fibonacci

Kỳ trước chúng ta đã học về dãy số Fibonacci và về một bài toán xếp hình. Hôm nay chúng ta sẽ sử dụng bài toán xếp hình này để chứng minh một hằng đẳng thức cho dãy số Fibonacci, đó là $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$

Một bài toán cũng như một bức tranh, muốn nhìn thấy vẻ đẹp của nó chúng ta nhìn nó ở nhiều góc cạnh khác nhau. Ví dụ như hằng đẳng thức mà chúng ta học ngày hôm nay, chúng ta có thể chứng minh nó bằng cách sử dụng công thức  $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$  rồi chúng ta đưa hai vế đẳng thức về bằng nhau qua một vài biến đổi đơn thuần đại số.

Nhưng thay vì chứng minh một cách "khô khan" bằng đại số như vậy, chúng ta sẽ dùng bài toán xếp hình mà chúng ta đã học ở bài trước để trình bày hai cách chứng minh cho hằng đẳng thức này. Hy vọng các bạn sẽ thấy cách chứng minh bằng tổ hợp này thú vị hơn.



Xin nhắc lại, dãy số Fibonacci là dãy số xác định theo quy luật sau: $$F_0 = 0, ~F_1 = 1, ~F_{n+1} = F_n + F_{n-1},$$  và vì vậy chúng ta có $$F_0 = 0, ~F_1 = 1, ~F_2 = 1, ~F_3 = 2, ~F_4 = 3, ~F_5 = 5, ~F_6 = 8, ~F_7 = 13, ~F_8 = 21, \dots$$


Chúng ta kiểm tra hằng đẳng thức $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}$$ với một vài giá trị của $n$ và $m$,

• Với $n=0$, $m=0$, hằng đẳng thức trở thành $$F_{2} = F_{1} F_{1} + F_{1} F_0 + F_0 F_{1}$$ chúng ta kiểm tra thấy cả hai vế của đẳng thức đúng là bằng $1$.

• Với $n=1$, $m=0$, $$F_{3} = F_{2} F_{1} + F_{2} F_0 + F_1 F_{1} = 2.$$

• Với $n=2$, $m=1$, $$F_{5} = F_{3} F_{2} + F_{3} F_1 + F_2 F_{2} = 5.$$

Dãy số Fibonacci có một ý nghĩa tổ hợp nhờ vào bài toán xếp hình sau đây

Bài toán xếp hình: Cho phép sử dụng hai loại gạch có kích thước $1 \times 1$ và $1 \times 2$, có bao nhiêu cách khác nhau để dùng hai loại gạch này xếp thành một hình chữ nhật có kích thước $1 \times n$?

Gọi $X_n$ là số cách xếp hình chữ nhật có kích thước $1 \times n$ bằng cách dùng hai loại gạch có kích thước $1 \times 1$ và $1 \times 2$. Chúng ta sẽ chứng minh rằng $X_n = F_{n+1}$.

Ví dụ, với $n=1,2,3,4$, chúng ta có $X_1 = F_2 = 1$, $X_2 = F_3 = 2$, $X_3 = F_4 = 3$, $X_4 = F_5 = 5$ như hình vẽ sau đây.

$n=4$: có 5 cách khác nhau để xếp hình chữ nhật có kích thước $1 \times 4$ bằng cách dùng hai loại gạch có kích thước $1 \times 1$ và $1 \times 2$.

Muốn tạo ra một hình chữ nhật $1 \times n$, đầu tiên chúng ta phải quyết định xem chúng ta sẽ tạo ra cái ô vuông đầu tiên bằng cách nào. Có hai cách. Chúng ta có thể dùng loại gạch $1 \times 1$ để tạo ra cái ô vuông đầu tiên, hoặc, chúng ta có thể dùng loại gạch $1 \times 2$.

Nếu chúng ta dùng loại gạch $1 \times 1$ để tạo ra cái ô vuông đầu tiên thì chúng ta còn lại $n-1$ ô vuông. Có bao nhiêu cách để tạo ra $n-1$ cái ô vuông tiếp theo? Đó chính là $X_{n-1}$ cách.

Còn nếu chúng ta dùng loại gạch $1 \times 2$ để tạo ra hai cái ô vuông đầu tiên thì chúng ta còn lại $n-2$ ô vuông. Có bao nhiêu cách để tạo ra $n-2$ ô vuông? Đó chính là $X_{n-2}$ cách.

Như vậy, tổng cọng chúng ta sẽ có $X_{n-1} + X_{n-2}$ cách. Vậy chúng ta rút ra được công thức $$X_n = X_{n-1} + X_{n-2}.$$

Từ đó chúng ta có  $$X_1 = 1, ~X_2 = 2, ~X_3 = 3, ~X_4 = 5, ~X_5 = 8, ~X_6 = 13, ~X_7 = 21, \dots$$

Như vậy $X_n = F_{n+1}$ - đó chính là số Fibonacci!!!

Bây giờ chúng ta trình bày hai cách chứng minh hằng đẳng thức $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$

Dùng bài toán xếp hình, chúng ta sẽ chứng minh rằng $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}.$$


Cách chứng minh thứ nhất.

Chúng ta đặt ra câu hỏi "Có bao nhiêu cách để xếp hình chữ nhật có kích thước $1 \times (n+m+1)$ như hình dưới đây?"

Rõ ràng câu trả lời là có $X_{n+m+1}$ cách để xếp hình chữ nhật $1 \times (n+m+1)$.

Bây giờ, chúng ta để ý cái ô vuông thứ $n+1$. Có ba trường hợp như hình vẽ sau đây.

Ở trường hợp thứ nhất, cái ô vuông thứ $n+1$ được lấp bởi viên gạch $1 \times 1$. Ở phía bên trái, chúng ta có $X_n$ cách để xếp hình chữ nhật $1 \times n$, còn ở phía bên phải, chúng ta có $X_m$ cách để xếp hình chữ nhật $1 \times m$. Như vậy ở trường hợp này, tổng cọng chúng ta có $X_{n} X_{m}$ cách.

Ở trường hợp thứ hai, cái ô vuông thứ $n+1$ được lấp bởi viên gạch $1 \times 2$. Ở phía bên trái, chúng ta có $X_n$ cách để xếp hình chữ nhật $1 \times n$, còn ở phía bên phải, chúng ta có $X_{m-1}$ cách để xếp hình chữ nhật $1 \times (m-1)$. Như vậy ở trường hợp này, tổng cọng chúng ta có $X_{n} X_{m-1}$ cách.

Tương tự ở trường hợp cuối cùng, chúng ta có $X_{n-1} X_{m}$ cách.

Tóm lại, tổng cọng chúng ta có $X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$ cách, và vì vậy chúng ta có hằng đẳng thức cần chứng minh $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}.$$


Cách chứng minh thứ hai.

Hằng đẳng thức $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$$ tương đương với hằng đẳng thức $$X_{n+m+1} = X_{n} X_{m+1} + X_{n-1} X_{m}.$$

Chúng ta sẽ chứng minh hằng đẳng thức thứ hai này bằng cách xem xét câu hỏi "Có bao nhiêu cách để xếp hình chữ nhật có kích thước $1 \times (n+m+1)$ như hình dưới đây?"

Rõ ràng câu trả lời là có $X_{n+m+1}$ cách để xếp hình chữ nhật $1 \times (n+m+1)$.


Bây giờ, chúng ta để ý cái rãnh ở vị trí thứ $n$. Có hai trường hợp như hình vẽ sau đây. Trường hợp thứ nhất là cái rảnh này không bị lấp bởi một viên gạch nào cả, còn trường hợp thứ hai là cái rảnh này bị lấp bởi viên gạch $1 \times 2$.

Ở trường hợp thứ nhất, chúng ta có $X_{n} X_{m+1}$ cách. Ở trường hợp thứ hai, chúng ta có $X_{n-1} X_{m}$ cách. Và tổng cọng, chúng ta có $X_{n} X_{m+1} + X_{n-1} X_{m}$ cách. Từ đó chúng ta rút ra hằng đẳng thức cần chứng minh $$X_{n+m+1} = X_{n} X_{m+1} + X_{n-1} X_{m}.$$

Vậy chúng ta đã trình bày xong hai cách chứng minh hằng đẳng thức bằng phương pháp tổ hợp $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$  

Nếu chúng ta cho $m=n$ thì chúng ta có hằng đẳng thức $$F_{2n+2} = F_{n+1}^2 + 2 F_{n+1} F_n.$$

Từ đây chúng ta có $$F_{2n+2} = (F_{n+1} + F_n)^2 - F_n^2$$ và chúng ta rút ra được một hằng đẳng thức mới là $$F_{2n+2} = F_{n+2}^2 - F_n^2.$$

Chúng ta tạm dừng ở đây, kỳ sau, chúng ta tiếp tục học về dãy số Fibonacci. Xin hẹn gặp lại các bạn.

Bài tập về nhà.

1. Dùng công thức  $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$  để chứng minh rằng 

$$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1},$$
$$F_{2n+2} = F_{n+2}^2 - F_n^2.$$

2. Dùng bài toán xếp hình để tìm ra các hằng đẳng thức khác cho dãy số Fibonacci.