Dãy Số Fibonacci Và Một Bài Toán Xếp Hình

Trang chủ » Công Thức Fibonacci » Dãy Số Fibonacci Và Một Bài Toán Xếp Hình

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

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}.$$ Labels: bài toán xếp hình, dãy số, đại số, Fibonacci, giai thừa, hằng đẳng thức, nhị thức Newton, quy nạp, rời rạc, sai phân, tam giác Pascal Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2013 (26)
    • ▼  tháng 2 (3)
      • Dãy số Fibonacci và tam giác Pascal
      • Hằng đẳng thức về dãy số Fibonacci
      • Dãy số Fibonacci và một bài toán xếp hình

English Version

English Version

Bài toán kết nối facebook

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

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

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... có bằng 1 không? (2015)

Hình tam giác

Bàn cờ vua và kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổng luỹ thừa

Số phức

Số phức

Công thức Moivre

Lượng giác

Công thức lượng giác cho góc bội

Công thức lượng giác Gauss cho 17-giác đều

Ngày số Pi (2016)

Radian là gì?

Số học

modulo - Phần 1

modulo - Phần 2

modulo - Phần 3

modulo - Phần 4

modulo - Phần 5

modulo - Phần 6

Số nguyên tố

Định lý Euclid về số nguyên tố

Một vài bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho số hữu tỷ II

Chứng minh lại định lý Wilson

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ thừa và định lý Wolstenholme

Câu đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ diệu của Euler

Tổ hợp

Bài toán kết nối facebook

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

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

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

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp

Điểm Fermat của hình tam giác

Điểm Fermat của hình tam giác II

Dựng hình

Dựng hình bằng thước và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

Công thức lượng giác Gauss cho 17-giác đều

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » Công Thức Fibonacci