Dãy số Fibonacci và một bài toán xếp hình


Hôm nay chúng ta sẽ học về dãy số Fibonacci và về một bài toán xếp hình. Các bạn sẽ thấy rằng bài toán xếp hình thoạt nghe qua thì không liên quan gì đến dãy số Fibonacci, nhưng cuối cùng đáp số của bài toán xếp hình lại chính là dãy số Fibonacci!

Trước tiên, chúng ta giới thiệu về dãy số Fibonacci. Dãy số Fibonacci $\{F_n\}$ được xác định theo công thức sau đây: $$F_0 = 0, ~F_1 = 1, ~F_{n+1} = F_n + F_{n-1}.$$

Do đó $$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$$



Dãy số Fibonacci có lẽ là dãy số nổi tiếng nhất trong toán học. Công thức tổng quát cho dãy số Fibonacci là như sau $$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 ta thay một vài giá trị của $n$ vào công thức trên để kiểm chứng xem công thức có đúng không nhé.
$$F_0 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^0 - \left( \frac{1 - \sqrt{5}}{2} \right)^0 \right] = \frac{1}{\sqrt{5}} (1-1) = 0$$ (Các bạn để ý rằng $a^0$ là bằng $1$ chứ không phải bằng $0$ nhé.)

$$F_1 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^1 - \left( \frac{1 - \sqrt{5}}{2} \right)^1 \right] = \frac{1}{\sqrt{5}} \left[  \frac{1 + \sqrt{5}}{2}  -  \frac{1 - \sqrt{5}}{2}  \right] = 1$$
$$F_2 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 \right] = \frac{1}{\sqrt{5}} \left[  \frac{6 + 2 \sqrt{5}}{4}  - \frac{6 - 2 \sqrt{5}}{4} \right] = 1$$
$$F_3 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 \right] = \frac{1}{\sqrt{5}} \left[  \frac{16 + 8 \sqrt{5}}{8}   -  \frac{16 - 8 \sqrt{5}}{8}  \right] = 2$$




Có nhiều cách để chứng minh công thức này. Ví dụ như các bạn có thể dùng phương pháp quy nạp chẳng hạn. Ở đây chúng ta sẽ trình bày một cách chứng minh trực tiếp bằng cách đặt $$A_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$ và chúng ta chứng minh rằng hai dãy số $\{F_n\}$ và $\{A_n\}$ là bằng nhau.

Để chứng minh hai dãy số $\{F_n\}$ và $\{A_n\}$ bằng nhau, chúng ta sẽ chứng minh rằng $A_0 = 0$, $A_1 = 1$ và $A_{n+1} = A_n + A_{n-1}$. Rõ ràng chỉ tồn tại duy nhất một dãy số thoã mãn điều kiện này, cho nên hai dãy số $\{F_n\}$ và $\{A_n\}$ bắt buộc phải bằng nhau.


Ở trên chúng ta đã kiểm chứng rằng $A_0 = 0$, $A_1 = 1$, do đó chúng ta chỉ cần chứng minh phần còn lại, đó là $A_{n+1} = A_n + A_{n-1}$. Để cho ngắn gọn, chúng ta sẽ đặt $$\alpha = \frac{1 + \sqrt{5}}{2} , ~~ \beta = \frac{1 - \sqrt{5}}{2},$$ và như vậy $$A_n = \frac{1}{\sqrt{5}} (\alpha^n - \beta^n).$$

Chúng ta có $$A_{n-1} + A_n = \frac{1}{\sqrt{5}} (\alpha^{n-1} - \beta^{n-1}) + \frac{1}{\sqrt{5}} (\alpha^n - \beta^n)= \frac{1}{\sqrt{5}} (\alpha^{n-1}(1+\alpha) - \beta^{n-1}(1+\beta)).$$

Các bạn có thể kiểm tra được rằng $\alpha$ và $\beta$ là hai nghiệm của phương trình bậc hai $x^2 - x - 1 = 0$, do đó $1 + \alpha = \alpha^2$ và $1 + \beta = \beta^2$, từ đó suy ra $$A_{n-1} + A_n = \frac{1}{\sqrt{5}} (\alpha^{n-1} \alpha^2 - \beta^{n-1} \beta^2) =  \frac{1}{\sqrt{5}} (\alpha^{n+1} - \beta^{n+1} ) = A_{n+1}.$$

Như vậy chúng ta đã chứng minh xong rằng hai dãy số $\{F_n\}$ và $\{A_n\}$ là bằng nhau. Từ đó chúng ta có 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].$$


Có lẽ các bạn đang tò mò là vì sao chúng ta có thể tìm ra được công thức này. Xin các bạn đón đọc các kỳ sau, chúng ta sẽ học cách để tìm công thức cho dãy số một cách tổng quát, ví dụ như tìm công thức cho các dãy số $a_{n+1} = 2 a_n + 5$, $b_{n+1} = 2 b_n - b_{n-1}$, $c_{n+2} = 2 c_{n+1} + c_{n} + 2 c_{n-1}$, v.v...




Bây giờ chúng ta xem xét bài toán xếp hình. Các bạn đã bao giờ chơi trò chơi điện tử Tetris chưa? Trò chơi Tetris là trò chơi xếp hình. Có nhiều loại gạch, ví dụ như gạch hình chữ I, T, L, v.v..., các viên gạch này sẽ từ từ rơi xuống. Người chơi phải điều khiển các viên gạch đang rơi này sao cho chúng rớt xuống vừa khít tạo thành càng nhiều các dãy liền mạch càng tốt.

Bài toán xếp hình mà chúng ta xem xét ở đây rất đơn giản chứ không phức tạp như trò chơi Tetris. Trong bài toán này, chúng ta chỉ được phép dùng hai loại gạch có kích thước $1 \times 1$ và $1 \times 2$. Câu hỏi đặt ra là có bao nhiêu cách khác nhau để chúng ta 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$.

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

Ở một bài viết trước, tôi có chia xẻ một kinh nghiệm của mình khi làm toán, đó là khi đối diện với một bài toán mà chúng ta chưa biết phải làm như thế nào, thì việc đầu tiên chúng ta có thể làm là xem xét các trường hợp đặc biệt của bài toán. Ở đây, đối với bài toán xếp hình, chúng ta sẽ giải bài toán cho từng giá trị của $n$, bắt đầu từ giá trị nhỏ nhất như $n=1,2,3$, rồi sau đó chúng ta sẽ tìm lời giải tổng quát cho mọi $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ẽ tìm giá trị của $X_1$, $X_2$, $X_3$, v.v...

  • Với $n=1$. Có bao nhiêu cách xếp hình chữ nhật có kích thước $1 \times 1$? Rõ ràng là có một cách duy nhất. Do đó $X_1 = 1$.

  • Với $n=2$. Có bao nhiêu cách xếp hình chữ nhật có kích thước $1 \times 2$? Có hai cách, cách thứ nhất là dùng hai viên gạch loại $1 \times 1$, cách thứ hai là dùng đúng một viên gạch loại $1 \times 2$. Như vậy $X_2 = 2$.

  • Với $n=3$. Chúng ta có ba cách như sau, do đó $X_3 = 3$.

  • Với $n=4$. Chúng ta có năm cách nên $X_4 = 5$.

Bây giờ chúng ta xem xét trường hợp tổng quát, đó là xếp hình chữ nhật $1 \times n$. Như hình dưới đây, để ý ô vuông đầu tiên. Chúng ta có thể dùng loại gạch $1 \times 1$ để lấp cái ô vuông đầu tiên, hoặc, chúng ta có thể dùng loại gạch $1 \times 2$ để lấp nó.


Nếu chúng ta dùng loại gạch $1 \times 1$ để lấp cái ô vuông đầu tiên thì chúng ta còn $n-1$ ô vuông tiếp theo cần được lấp. Có bao nhiêu cách để lấp $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$ để lấp hai cái ô vuông đầu tiên thì chúng ta còn $n-2$ ô vuông. Có bao nhiêu cách để lấp $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 thì $X_n = X_{n-1} + X_{n-2}$.

Chúng ta đã tìm ra quy luật của số $X_n$: $$X_1 = 1, X_2 = 2, X_n = X_{n-1} + X_{n-2}.$$

Vậy thì $$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!!!

Tóm lại câu trả lời cho bài toán xếp hình là, 
Có $F_{n+1}$ cách khác nhau để xếp được một hình chữ nhật có kích thước $1 \times n$ từ hai loại gạch có kích thước $1 \times 1$ và $1 \times 2$.

Các bạn thấy có thú vị không? Một bài toán xếp hình, thoạt nhìn có vẻ như không liên quan gì đến số Fibonacci, nhưng đáp số lại là số Fibonacci! 

Dùng bài toán xếp hình này, chúng ta có thể chứng minh được những đẳng thức rất thú vị về dãy số Fibonacci. Ở phần bài tập về nhà chúng ta sẽ liệt kê một số các đẳng thức này.

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

Dùng bài toán xếp hình để chứng minh rằng 
$$F_{2n+2} = F_{n+1}^2 + 2 F_{n+1} F_n,$$
$$F_{2n+2} = F_{n+2}^2 - F_n^2,$$
$$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1},$$
$${2011 \choose 0} + {2010 \choose 1} + {2009 \choose 2} + {2008 \choose 3} + \dots + {1007 \choose 1004} + {1006 \choose 1005} = F_{2012},$$
$${2012 \choose 0} + {2011 \choose 1} + {2010 \choose 2} + {2009 \choose 3} + \dots + {1007 \choose 1005} + {1006 \choose 1006} = F_{2013}.$$