Dãy số Fibonacci và tam giác Pascal


Kỳ trước chúng ta đã sử dụng kết quả của bài toán xếp hình để chứng minh các hằng đẳng thức cho dãy số Fibonacci. Hôm nay chúng ta tiếp tục đề tài này. Chúng ta sẽ chứng minh các hằng đẳng thức sau $${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}.$$
Một cách tổng quát, chúng ta có hằng đẳng thức $$\sum_{v+u=n}{v \choose u} = F_{n+1}.$$ Thông qua hằng đẳng thức này chúng ta thấy một mối liên hệ thú vị giữa dãy số Fibonnaci và tam giác số Pascal.


Trước hết 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$$

Xin giới thiệu với các bạn ký hiệu $n!$, đọc là $n$ giai thừa, công thức của nó là như sau $$n! = 1 \times 2 \times 3 \times \dots \times n.$$
Chú ý rằng theo quy định chúng ta có $0!=1$ (chứ không phải $0!=0$ đâu nhé!)
Như vậy $$0! = 1, ~~ 1! = 1, ~~ 2! = 2, ~~ 3! = 6, ~~ 4! = 24, ~~ 5! = 120, \dots $$

Tiếp theo, chúng ta có ký hiệu ${n \choose k}$. Công thức của nó là $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ 

Ví dụ, các bạn có thể kiểm tra rằng $${4 \choose 0} = \frac{4!}{0! 4!} = 1, ~~{4 \choose 1} = \frac{4!}{1! 3!} = 4, ~~{4 \choose 2} = \frac{4!}{2! 2!} = 6, ~~{4 \choose 3} = \frac{4!}{3! 1!} = 4, ~~{4 \choose 4} = \frac{4!}{4! 0!} = 1.$$

Ký hiệu ${n \choose k}$ đọc là "$n$ chọn $k$", lý do là vì ${n \choose k}$ chính là số cách chọn $k$ đồ vật (không kể tính thứ tự) trong số $n$ đồ vật. Ví dụ, nếu chúng ta có $4$ con cá và muốn chọn ra $2$ con cá thì sẽ có đúng ${4 \choose 2} = 6$ cách chọn.


có đúng ${4 \choose 2} = 6$ cách chọn ra $2$ con cá từ $4$ con cá
Lưu ý rằng các sách viết ở Việt Nam thường dùng ký hiệu $C^k_n$ thay vì là ${n \choose k}$.


Các số ${n \choose k}$ chính là các hệ số trong khai triển nhị thức Newton. Chúng tạo nên tam giác số nổi tiếng - tam giác số Pascal.



Nếu chúng ta đánh số thứ tự cho hình tam giác Pascal như hình sau đây. Khởi đầu bằng hàng số 0, hàng số 1, hàng số 2, v.v..., và trên mỗi hàng, chúng ta có số thứ 0, số thứ 1, số thứ 2, v.v... Vậy thì số thứ $k$ nằm trên hàng thứ $n$ chính là bằng ${n \choose k}$.

Ví dụ, chúng ta thấy trên hàng thứ $4$, chúng ta có số $1$, $4$, $6$, $4$, $1$, đó chính là ${4 \choose 0}$, ${4 \choose 1}$, ${4 \choose 2}$, ${4 \choose 3}$, ${4 \choose 4}$.



Hằng đẳng thức mà chúng ta học ngày hôm nay đó là $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$

Lấy một vài ví dụ khi $n=0,1,2,\dots,6$ chúng ta có $$F_1 = {0 \choose 0}, ~~F_2 = {1 \choose 0}, ~~F_3 = {2 \choose 0} + {1 \choose 1}, ~~F_4 = {3 \choose 0} + {2 \choose 1},$$ $$F_5 = {4 \choose 0} + {3 \choose 1} + {2 \choose 2}, ~~F_6 = {5 \choose 0} + {4 \choose 1} + {3 \choose 2},$$ $$F_7 = {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3}$$

Các đẳng thức này cho ta thấy một mối liên hệ thú vị giữa tam giác số Pascal và dãy số Fibonacci. Hình vẽ sau đây minh hoạ điều đó. Nếu chúng ta cọng các số trong tam giác Pascal theo đường chéo như trong hình vẽ thì chúng ta sẽ có tổng là các số Fibonacci.
Tổng theo đường chéo: $F_7 = {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3}=13$



Chứng minh hằng đẳng thức.

Chúng ta sẽ dùng bài toán xếp hình để chứng minh hằng đẳng thức. Xin nhắc lại, 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$?
$X_1=1$, $X_2 = 2$, $X_3=3$, $X_4=5$.

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 thấy rằng 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 tạo ra hình chữ nhật $1 \times n$. Vì vậy chúng ta có công thức $$X_n = X_{n-1} + X_{n-2}.$$
Tức là $$X_1 = 1, ~~X_2 = 2, ~~X_3 = 3, ~~X_4 = 5, ~~X_5 = 8, \dots$$
Từ đó suy ra $$X_n = F_{n+1}.$$
Vậy muốn chứng minh hằng đẳng thức, chúng ta cần phải chứng minh $$X_{n} = \sum_{v+u=n}{v \choose u}.$$


Chúng ta để ý rằng nếu chúng ta xây dựng một hình chữ nhật $1 \times n$ bằng cách sử dụng $v$ viên gạch, trong đó $u$ viên gạch có dạng $1 \times 2$ và $(v-u)$ viên gạch có dạng $1 \times 1$, thì bằng cách cọng tổng độ dài các viên gạch lại chúng ta có $$n = 2 \times u + 1 \times (v-u).$$
Tức là $$u + v = n.$$


Bây giờ chúng ta nhìn hình vẽ sau. Chúng ta có $v$ vị trí cho $v$ viên gạch. Trong $v$ vị trí này chúng ta phải chọn ra $u$ vị trí mà chúng ta sẽ dùng viên gạch $1 \times 2$. (Còn $(v-u)$ vị trí còn lại sẽ là loại gạch $1 \times 1$.) Có nghĩa là trong $v$ "con cá", chúng ta phải chọn ra $u$ "con cá". Có bao nhiêu cách chọn? Chính là ${v \choose u}$ cách chọn.

Vì vậy nên tổng số các cách tạo ra hình chữ nhật $1 \times n$ sẽ là $$\sum_{v+u=n}{v \choose u}.$$

Và cuối cùng chúng ta sẽ có hằng đẳng thức $$X_{n} = \sum_{v+u=n}{v \choose u}.$$





Vậy chúng ta đã trình bày xong một cách chứng minh hằng đẳng thức sau bằng phương pháp tổ hợp $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$

Ví dụ với $n=2011$ và $n=2012$ chúng ta có hằng đẳng thức thú vị sau đây $${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}.$$



Chúng ta tạm dừng ở đây, kỳ sau, chúng ta sẽ học thêm về dãy số. Các bạn còn nhớ công thức cho dãy số Fibonacci không? Đó 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]$$
Nếu các bạn tò mò muốn biết vì sao chúng ta có thể tìm ra được công thức kỳ lạ này, thì các bạn hãy đón đọc các kỳ sau. Chúng ta sẽ học cách tìm công thức cho một dãy số tổng quát. Xin hẹn gặp lại các bạn.




Bài tập về nhà.

Sử dụng tính chất của tam giác Pascal để tìm cách chứng minh khác cho hằng đẳng thức $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$