Hôm nay bọn họ sẽ học về hàng số Fibonacci và về một câu hỏi xếp hình. Các bạn sẽ thấy rằng câu hỏi xếp hình thoạt nghe qua thì không liên quan gì cho dãy số Fibonacci, nhưng cuối cùng đáp số của câu hỏi xếp hình lại chính là dãy số Fibonacci!Trước tiên, họ giới thiệu về dãy số Fibonacci. Dãy số Fibonacci $F_n$ được khẳng định theo cách làm 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 chắc rằng là hàng số danh tiếng nhất vào toán học. Công thức tổng thể cho dãy số Fibonacci là như sau $$F_n = frac1sqrt5 left< left( frac1 + sqrt52 ight)^n - left( frac1 - sqrt52 ight)^n ight>$$Chúng ta núm một vài quý giá 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 = frac1sqrt5 left< left( frac1 + sqrt52 ight)^0 - left( frac1 - sqrt52 ight)^0 ight> = frac1sqrt5 (1-1) = 0$$(Các bạn lưu ý rằng $a^0$ là bằng $1$ chứ không hẳn bằng $0$ nhé.)$$F_1 = frac1sqrt5 left< left( frac1 + sqrt52 ight)^1 - left( frac1 - sqrt52 ight)^1 ight> = frac1sqrt5 left< frac1 + sqrt52 - frac1 - sqrt52 ight> = 1$$$$F_2 = frac1sqrt5 left< left( frac1 + sqrt52 ight)^2 - left( frac1 - sqrt52 ight)^2 ight> = frac1sqrt5 left< frac6 + 2 sqrt54 - frac6 - 2 sqrt54 ight> = 1$$$$F_3 = frac1sqrt5 left< left( frac1 + sqrt52 ight)^3 - left( frac1 - sqrt52 ight)^3 ight> = frac1sqrt5 left< frac16 + 8 sqrt58 - frac16 - 8 sqrt58 ight> = 2$$Có nhiều cách để chứng minh cách làm này. Ví dụ như các bạn có thể dùng phương pháp quy hấp thụ chẳng hạn. Ở đây họ sẽ trình diễn một cách minh chứng trực tiếp bằng phương pháp đặt $$A_n = frac1sqrt5 left< left( frac1 + sqrt52 ight)^n - left( frac1 - sqrt52 ight)^n ight>$$ và bọn họ chứng minh rằng hai hàng số $F_n$ cùng $A_n$ là bởi nhau.Để chứng tỏ hai hàng số $F_n$ cùng $A_n$ bằng nhau, chúng ta sẽ chứng tỏ rằng $A_0 = 0$, $A_1 = 1$ với $A_n+1 = A_n + A_n-1$. Ví dụ chỉ tồn tại tốt nhất một dãy số thoã mãn điều kiện này, cho nên vì thế hai hàng số $F_n$ với $A_n$ sẽ phải bằng nhau.Ở trên họ đã kiểm chứng rằng $A_0 = 0$, $A_1 = 1$, vì chưng đó chúng ta chỉ cần chứng minh phần còn lại, sẽ là $A_n+1 = A_n + A_n-1$. Để mang lại ngắn gọn, bọn họ sẽ để $$alpha = frac1 + sqrt52 , ~~ eta = frac1 - sqrt52,$$ và vậy nên $$A_n = frac1sqrt5 (alpha^n - eta^n).$$Chúng ta tất cả $$A_n-1 + A_n = frac1sqrt5 (alpha^n-1 - eta^n-1) + frac1sqrt5 (alpha^n - eta^n)= frac1sqrt5 (alpha^n-1(1+alpha) - eta^n-1(1+eta)).$$Các bạn cũng có thể kiểm tra được rằng $alpha$ với $eta$ là nhì nghiệm của phương trình bậc hai $x^2 - x - 1 = 0$, vì thế $1 + alpha = alpha^2$ với $1 + eta = eta^2$, từ đó suy ra $$A_n-1 + A_n = frac1sqrt5 (alpha^n-1 alpha^2 - eta^n-1 eta^2) = frac1sqrt5 (alpha^n+1 - eta^n+1 ) = A_n+1.$$Như vậy họ đã chứng minh xong xuôi rằng hai hàng số $F_n$ và $A_n$ là bởi nhau. Trường đoản cú đó chúng ta có cách làm $$F_n = frac1sqrt5 left< left( frac1 + sqrt52 ight)^n - left( frac1 - sqrt52 ight)^n ight>.$$
Có lẽ chúng ta đang tò mò và hiếu kỳ là vì sao chúng ta cũng có thể tìm ra được phương pháp này. Xin các bạn đón đọc các kỳ sau, họ sẽ học phương pháp để tìm bí quyết cho dãy số một bí quyết tổng quát, ví như tìm công thức cho những 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ạn đang xem: Số fibonacci


Bây giờ bọn họ xem xét vấn đề xếp hình. Các bạn đã lúc nào chơi trò nghịch điện tử Tetris chưa? Trò nghịch Tetris là trò nghịch xếp hình. Có khá 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 ốp này đã từ từ rơi xuống. Fan chơi phải điều khiển và tinh chỉnh các viên gạch đang rơi này làm sao cho chúng rớt xuống vừa khít tạo thành càng nhiều các dãy lập tức mạch càng tốt.
Bài toán xếp hình mà họ xem xét tại đây rất đơn giản dễ dàng chứ không phức tạp như trò nghịch Tetris. Trong câu hỏi này, họ chỉ được phép sử dụng hai các loại gạch có kích thước $1 imes 1$ và $1 imes 2$. Thắc mắc đặt ra là gồm bao nhiêu cách khác biệt để họ dùng hai một số loại gạch này xếp thành một hình chữ nhật có kích cỡ $1 imes n$.
*

Bài toán xếp hình: có thể chấp nhận được sử dụng hai một số loại gạch có form size $1 imes 1$ và $1 imes 2$, bao gồm bao nhiêu cách khác nhau để dùng hai một số loại gạch này xếp thành một hình chữ nhật có size $1 imes n$?
Ở một bài viết trước, tôi tất cả chia bửa một kinh nghiệm của bản thân khi làm toán, đó là lúc đối diện với một vấn đề mà bọn họ chưa biết nên làm như thế nào, thì vấn đề đầu tiên chúng ta có thể làm là coi xét những trường hợp đặc trưng của bài bác toán. Ở đây, so với bài toán xếp hình, bọn họ sẽ giải bài toán cho từng quý hiếm của $n$, bắt đầu từ giá trị nhỏ dại nhất như $n=1,2,3$, rồi sau đó bọn họ sẽ tìm giải thuật tổng quát tháo cho những $n$.
Gọi $X_n$ là số giải pháp xếp hình chữ nhật có size $1 imes n$ bằng cách dùng hai loại gạch có kích cỡ $1 imes 1$ với $1 imes 2$. Bọn họ sẽ tìm quý giá của $X_1$, $X_2$, $X_3$, v.v...
Với $n=1$. Bao gồm bao nhiêu giải pháp xếp hình chữ nhật có size $1 imes 1$? ví dụ là bao gồm một bí quyết duy nhất. Vì vậy $X_1 = 1$.
*

Với $n=2$. Tất cả bao nhiêu giải pháp xếp hình chữ nhật có kích thước $1 imes 2$? tất cả hai cách, cách trước tiên là cần sử dụng hai viên gạch loại $1 imes 1$, bí quyết thứ nhì là cần sử dụng đúng một viên gạch nhiều loại $1 imes 2$. Vậy nên $X_2 = 2$.
*

*

*

Bây giờ họ xem xét trường đúng theo tổng quát, chính là xếp hình chữ nhật $1 imes n$. Như hình bên dưới đây, lưu ý ô vuông đầu tiên. Chúng ta có thể dùng loại gạch $1 imes 1$ để lấp chiếc ô vuông đầu tiên, hoặc, chúng ta cũng có thể dùng một số loại gạch $1 imes 2$ để bao phủ nó.
Nếu chúng ta dùng nhiều loại gạch $1 imes 1$ nhằm lấp mẫu ô vuông trước tiên thì họ còn $n-1$ ô vuông tiếp theo sau cần được lấp. Có bao nhiêu phương pháp để lấp $n-1$ dòng ô vuông tiếp theo? Đó chính là $X_n-1$ cách.

Xem thêm: Vận Dụng Cơ Sở Hạ Tầng Và Kiến Trúc Thượng Tầng, TiểU LuậN


Còn nếu bọn họ dùng một số loại gạch $1 imes 2$ để bao phủ hai cái ô vuông trước tiên thì chúng ta còn $n-2$ ô vuông. Tất cả bao nhiêu phương pháp để lấp $n-2$ ô vuông? Đó đó là $X_n-2$ cách.