Luận văn Một số đồng nhất thức của số Fibonacci và ứng dụng

1gcd(F ,F ) 1.  (1.4) Chứng minh: Thang Long University Library 19 Với n=0 ta có 0 1gcd(F ,F) gcd(0,1) 1.  (mệnh đề đúng). Giả sử mệnh đề đúng với .n k(k 0 N,k )  tức là: gcd k k 1(F ,F ) 1  ,(giả thiết quy nạp). Ta cần chứng minh mệnh đề đúng với n k 1  , tức là k 1 k 2gcd(F ,F ) 1.   Giả sử có một số nguyên dương d thỏa mãn d 1 và d là ước số chung của k 1F  và k 2F . Ta có k 2 k k 1F F F   Vì vậy, nếu d là ước số chung của k 1F  và k 2F , theo đó kF cũng chia hết cho d. Điều này lại mâu thuẫn với giả thiết k k 1gcd(F ,F ) 1.  Do đó, n n 1gcd(F ,F ) 1  , với n ≥ 0. □ Tính chất. 1.6.2. Với n ≥ 0, ta có: n n 2gcd(F ,F ) 1.  (1.5) Chứng minh: Với n 0 ta có 0 2gcd(F ,F ) gcd(0,1) 1.  (mệnh đề đúng). Giả sử mệnh đề đúng với .n k(k 0 N,k )  tức là: gcd k k 2(F ,F ) 1  , (giả thiết quy nạp). Ta cần chứng minh mệnh đề đúng với n k 1  , tức là k 1 k 3gcd(F ,F ) 1.   Giả sử có một số nguyên dương d thỏa mãn d 1 và d là ước số chung của k 1F  và k 3F . Ta có: k 3 k 1 k 2F F F    Vì vậy, nếu d là ước số chung của k 1F  và k 3F , theo đó k 2F  cũng chia hết cho d. Mà k 2 k k 1F F F   suy ra kF cũng chia hết cho d. Điều này lại mâu thuẫn với giả thiết k k 2gcd(F ,F ) 1.  20 Do đó, n n 2gcd(F ,F ) 1  , với n ≥ 0. □ Ta có một số khai triển sau. 50 1 2 3 4F F F F F F 0 1 1 2 3 5 12 4.3             51 2 3 4 6F F F F F F 1 1 2 3 5 8 20 4.5             5 72 3 4 6F F F F F F 1 2 3 5 8 13 32 4.8             Những kết quả này cho ta những tính chất dưới đây: Tính chất. 1.6.3. Tổng của sáu số Fibonacci liên tiếp bất kỳ chia hết cho 4. Với n ≥ 0, ( n cố định), ta có đẳng thức sau: 5 n r n n 5n 1 n 2 n 3 n 4 n 4 r 0 F F F F F F F 4F              (1.6) Chứng minh: Với n ≥ 0, ta có vế trái bằng 5 n r n n 5n 1 n 2 n 3 n 4 r 0 F F F F F F F            n n 1 n 2 n 3 n 4 n 3 n 4(F F ) F F F (F F )            n 2 n 3 n 4 n 2 n 3 n 42F 2F 2F 2(F F ) 2F           n 44F . □ Do đó 5 n r n n 5n 1 n 2 n 3 n 4 n 4 r 0 F F F F F F F 4F              Tính chất. 1.6.4. Tổng của mười số Fibonacci liên tiếp bất kỳ chia hết cho 11. Với n ≥ 0, (n cố định), ta có đẳng thức sau: 9 n r n 6 r 0 F 11F    (1.7) Chứng minh: Thang Long University Library 21 Với n ≥ 0,(n cố định), Ta có: 5 n r n n 5n 1 n 2 n 3 n 4 n 4 r 0 F F F F F F F 4F              (theo tính chất 1.6.3) Suy ra n n 5n 1 n 2 n 3 n 4 n 6 n 4 n 6F F F F F F F 4F F              Mà ta có : n 7 n 5 n 7 n 7n 8 n 9 n 6 n 6 n 8F F F F F F F F F               n 7 n 5n 6 n 82F 2F F F      n 5 n 7 n 5n 6 n 6 n 62F 2(F F ) F F F          n 5 n 7n 65F 3F F    n 5 n 5n 6 n 65F 3F F F      n 5n 66F 4F   Suy ra 9 n r n 5n 4 n 6 n 6r 0 .F 4F F 6F 4F        n 5n 4 n 6 n 6 n 6 n 64(F F ) 7F 4F 7F 11F .          □ Do đó “Tổng của mười số Fibonacci liên tiếp bất kỳ chia hết cho 11”. Ta có 0 1 2 4F F F 2 3 1 F 1       50 1 2 3F F F F 4 5 1 F 1        0 1 2 3 4 6F F F F F 7 8 1 F 1.         Tính chất. 1.6.5. Với n ≥ 0, ta có đẳng thức sau: n r n 2 r 0 F F 1    (1.8) Chứng minh: Công thức tổng quát này có thể được thiết lập bằng cách sử dụng các phương pháp quy nạp của toán học, ở đây ta chọn cách sử dụng định nghĩa truy hồi của số Fibonacci xét những đẳng thức sau đây: 0 2 1F F F  22 1 3 2F F F  2 4 3F F F  . . . . . . . . . nn 1 n 1F F F   n n 2 n 1F F F   Cộng tất cả các đẳng thức ở vế bên trái cho chúng ta kết quả: n rr 0 F ,  tổng tất cả các đẳng thức ở vế phải cho ta kết quả là: n2 1 3 2 n 1 n 2 n 1 n n1 2 2 3 3 n 1 n 1 n 2 n 2 1 n 2 (F F )+(F F ) (F F ) (F F ) F (F F ) (F F ) · · · (F F ) (F F ) F F F F 1                               . Do đó, với n ≥ 0, ta có n r n 2 r 0 F F 1    . □ Khai triển từ lũy thừa bậc nhất lên bình phương ta có: 2 20F 0 0 0 1    2 2 2 20 1F F 0 1 1 1 1      2 2 2 2 2 20 1 2F F F 0 1 1 2 1 2        2 2 2 2 2 2 2 20 1 2 3F F F F 0 1 1 2 6 2 3          2 2 2 2 2 2 2 2 2 20 1 2 3 4F F F F F 0 1 1 2 3 15 3 5            Từ những kết quả của năm đẳng thức trên, ta có tính chất sau: Tính chất. 1.6.6. Với n ≥ 0, ta có đẳng thức sau: n 2 r n n 1r 0 F F F .   (1.9) Chứng minh: Thang Long University Library 23 Chứng minh bằng phương pháp quy nạp của toán học. Với n = 0, ta có 0 2 2 2 r 0 0 1 0 0 1r 0 F F 0 0 1 F F F F          ( đẳng thức luôn đúng ). Giả sử đẳng thức trên đúng với .n k(k 0 N,k )  Ta có: k 2 r k k 1r 0 F F F    (giả thiết quy nạp) Ta phải chứng minh đẳng thức đúng với n = k + 1 (≥ 1), tức là k 1 2 r k 1 k 2r 0 F F F .      Thật vậy ta có : k 1 k2 2 2 2 r r k 1 k k 1 k 1r 0 r 0 F F F (F F ) F                  k 1 k k 1 k 1 k 2F (F F ) F F .        □ Do đó, với n ≥ 0, n 2 r n n 1r 0 F F F .   Dựa theo tài liệu tham khảo [3],[4]. Tính chất 1. 6.7. Với n 1, ta có đẳng thức sau: n 2r 1 1 3 2n 1 2nr 1 F F F F F .      (1.10) Chứng minh. Ta có: 24 2 2 1 2 3 4 2 5 6 4 2 3 2 2 2 4 2 1 2 ... ... ...               n n n n n n F F F F F F F F F F F F F F Cộng tất cả các đẳng thức vế bên trái cho chúng ta n 2r 1 r 1 F ,   tổng tất cả các đẳng thức ở vế phải cho ta kết quả là: 2 2 4 4 2n 4 2n 4 2n 2 2n 2 2n 2n(F F ) (F F ) · · · (F F ) (F F ) F F             Do đó, với n 1, n 2r 1 1 3 2n 1 2nr 1 F F F F F .      □ Tính chất 1.6.8. Với n 1, ta có đẳng thức sau: n 2r 2 4 2n 2n 1r 1 F F F F F 1.      (1.11) Chứng minh. Với n 1 ta có vế trái 2F 1 Vế phải 3F 1 2 1 1    nên 2 3F F 1  (mệnh đề đúng). Giả sử mệnh đề đúng với n k(k 1,k N)   tức là: k 2r 2 4 2k 2k 1r 1 F F F F F 1      (giả thiết quy nạp). Ta cần chứng minh mệnh đề đúng với n k 1  tức là 2 4 2k 2k 2 2k 3(F F ... F ) F F 1.       Thật vậy ta có 2 4 2k 2k 2 2k 1 2k 2 2k 3(F F ... F ) F F 1 F F 1.            □ Tính chất 1.6.9. Với n 1, ta có đẳng thức sau: 2 nnn 1 n 1F F F ( 1) .     (1.12) Thang Long University Library 25 Chứng minh. Với n 1 , ta có 2 2 1 0 2 1F .F F 0.1 1 1 ( 1)       (mệnh đề đúng). Giả sử mệnh đề đúng với n k(k 1 N,k )   tức là: 2 kk 1 k 1 kF F F ( 1)     (giả thiết quy nạp). Ta cần chứng minh mệnh đề đúng với n k 1,  tức là 2 k 1k k 2 k 1F .F F ( 1) .      Ta có: 2 2 k k 2 k 1 k 1 k 2 k 1 k k k 1 F .F F (F F )(F F ) (F F )           2 2k 1 k 1 k 1 k k 2 k 1 k 2 k k k 1 k k 1F .F F .F F .F F .F F F 2F .F              2 2k 1 k 1 k k 2 k k 1 k 2 k 1 k 1 k(F .F F ) (F .F F ) F .F F .F            = k k 1 k 2 k k 1 k 1 k( 1) ( 1) F (F F ) F F           2k 2 k k 2 k 1 k 1 k 1 k 2F F F F F F F         k 1 k 12F F F ( 1) ( 1) k 2 k k 1          . □ Từ đó ta có điều phải chứng minh. 26 CHƯƠNG 2. MỘT SỐ ỨNG DỤNG CỦA SỐ FIBONACCI. Chương này sẽ cung cấp một số ứng dụng mà các số Fibonacci xuất hiện, dựa trên tài liệu tham khảo [1], [2], [3], [5], [7] 2.1. TẬP CON CỦA nS KHÔNG CHỨA HAI SỐ NGUYÊN LIÊN TIẾP. Với n ≥ 1, cho  nS 1, 2, 3, ... ,, n và cho 0S , là tập hợp rỗng. Vậy số lượng các tập con của nS là n.2 Tìm số lượng các tập con của nS không chứa hai số nguyên liên tiếp. Với n ≥ 0, gọi na là số lượng các tập con của nS không chứa hai số nguyên liên tiếp. Xét trường hợp với n = 3, 4, và 5. Ta có các tập con không chứa hai số nguyên liên tiếp với ba trường hợp cụ thể dưới đây: Với n = 3: 3S = {1, 2, 3} các tập con: ∅, {1}, {2}, {3}, {1, 3} Với n = 4: 4S = {1, 2, 3, 4} các tập con: ∅, {1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4} Với n = 5: 5S = {1, 2, 3, 4, 5} các tập con: ∅, {1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4}, {5}, {1, 5}, {2, 5}, {3, 5}, {1, 3, 5} Xét các trường hợp n = 5, chỉ có hai trường hợp có thể xảy ra, và chúng không thể xảy ra đồng thời: (i) Số 5 không ở trong tập hợp con: Chúng ta có thể nhận thấy và sử dụng tám tập con cho trong 4S , như ở dòng đầu tiên của tập con cho trong 5S . (ii) Số 5 ở trong tập hợp con: Vì thế không thể có số 4 trong tập hợp con. Vì vậy, ta đặt số nguyên 5 trong mỗi một tập hợp con trong năm tập con Thang Long University Library 27 cho trong 3S và đó là năm tập con ở dòng thứ hai của các tập con cho trong 5S . Do đó, ta có 5 4 3a a a .  Trường hợp tổng quát. Gọi na là số lượng tập con của nS không chứa hai số nguyên liên tiếp, chỉ có hai trường hợp có thể xảy ra, và chúng không thể xảy ra đồng thời: Trường hợp 1: Số n không ở trong tập hợp con, khi đó có n 1a  tập con như vậy. Trường hợp 2: Số n ở trong tập con, vì thế không thể có số n 1 trong tập hợp con. Do đó có n 2a  tập con như vậy. Kết quả là: n n 1 n 2 0 1a a a , n 2, a 1, a 2      Mối quan hệ truy hồi trong trường hợp này là một dãy những con số Fibonacci. Ở đây ta có 0 2a 1 F  và 1 3a 2 F .  Do đó, n n 2 .a F , n 0  28 2.2. SỐ LƯỢNG CÁC TẬP HỢP SINH CỦA n 1S  . Cho nS = {1, 2, 3,. . . , n}, với n ≥ 1. Với bất kỳ tập con A khác rỗng của nS , ta định nghĩa .A 1 {a 1 A}| a   Do đó, với n ≥ 1, ta gọi ng là số lượng các tập con A khác rỗng của nS sao cho n 1A (A 1) S .   Những tập con A khác rỗng của nS có tính chất như trên được gọi là tập hợp sinh của n 1S . Ta thấy rằng đối với bất kỳ tập con A là tập hợp sinh ta có, 1 A và, đối với n ≥ 2, .n A Ta xét n = 3, 4, và 5, ta thấy các tập hợp có tính chất trên: + Với n = 3: ta có tập hợp sinh của S4; A= {1, 3} thì A + 1 = {2, 4}, khi đó: 4A (A 1) S .   Và A = {1, 2, 3} thì A + 1 = { 2, 3, 4}, khi đó: 4A (A 1) S .   Do đó: 3g 2 + Với n = 4: ta có các tập hợp sinh của S5 là các tập sau: A = {1, 2, 4} thì A + 1 = {2, 3, 5}, ta thấy rằng 5A (A 1) S .   và A= {1, 3, 4} thì A + 1 = {2, 4, 5}, ta thấy rằng. A (A 1) S 5    và A= {1, 2, 3, 4} thì A + 1 = {2, 3, 4, 5}, và ta thấy rằng 5A (A 1) S .   Thang Long University Library 29 Do đó: 4g 3 Tương tự với n = 5 ta có các tập hợp sinh của S6 là: {1, 3, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {1, 2, 3, 4, 5}. Ở đây ta thấy khi n = 5 ta có các tập hợp sinh của S6 được tạo nên bằng cách đặt 5 vào trong mỗi tập hợp sinh của S5 và S4. Do đó: 5 4 3g g g  và trường hợp cụ thể này khái quát hóa cho ta cách xác định số lượng tập hợp sinh ng bằng cách đặt số n vào trong mỗi tập hợp sinh của Sn và Sn-1. Khi đó n n 1 n 2 1 g g g , n 3, g 1       (với A={1}), 2 g 1 (với A= {1, 2}). Thật vậy: Chứng minh rằng:    n n 1 n 2g g g , n 3 . Hay chứng minh rằng:   n 2 n 1 ng g g Giả sử: A sinh ra gn     nA (A 1) g B sinh ra gn+1     n 1B (B 1) g + A sinh ra gn     nA (A 1) g                    n n 2 C A n 1 C 1 (A 1) n 1 n 2 C (C 1) A n 1 (A 1) n 1 n 2 A (A 1) n 1 n 2 g n 1 n 2 g                                      Gäi Vậy nếu A sinh ra gn thì  A n 1  sinh ra gn+2 30                   n 1 n 1 n 2 D B n 1 D 1 (B 1) n 2 D (D 1) B n 1 (D 1) n 2 B (B 1) n 1 n 2 g n 1 n 2 g n 2 g                                       Gäi: Vậy nếu B sinh ra gn+1 thì  B n 1  sinh ra gn+2 + B sinh ra gn+1 n 1B B 1 g     : Nếu một tập M sinh ra   n 2 M N n 1 g n 1 N         n (N 1) n 1 N       N ít nhất cũng sinh ra gn. Điều này cho ta thấy nếu A sinh ra gn hoặc gn+1 thì  A n 1  sinh ra gn+2 và ngược lại. □ (Lưu ý quy ước 0g 0, sau đó mở rộng các mối quan hệ truy hồi đến n ≥ 2. và giải phương trình 0 2 1g g g  để có được 0 .g 1 1 0)   Ở đây ta thấy rằng n ng F , n ≥1. 2.3. CHUỖI NHỊ PHÂN ĐỘ DÀI n KHÔNG CÓ HAI SỐ 1 LIÊN TIẾP. Xét các chuỗi nhị phân tạo thành từ 0 và 1. Đối với n ≥ 1, có n2 chuỗi nhị phân độ dài n, đó là, các chuỗi được tạo thành từ n ký hiệu, có thể là 0 hoặc là 1. Tìm những chuỗi nhị phân có độ dài n, mà không có hai số 1 liên tiếp. Ta gọi nb là số lượng các chuỗi nhị phân có độ dài n không có hai số 1 liên tiếp và tìm hiểu, các trường hợp cụ thể sau. (i) Với 3b = 5, ta có các chuỗi 000, 100, 010, 001, 101; và Thang Long University Library 31 (ii) Với 4b = 8, ta có các chuỗi 0000, 1000, 0100, 0010, 0001, 1010, 1001, 0101. Tổng quát, khi n ≥ 2, ta có hai trường hợp để xem xét cho một chuỗi s có độ dài n mà không có hai số 1 liên tiếp : Trường hợp 1: s có chữ số tận cùng là số 0. Ta có n 1b  chuỗi như vậy, nhận được bằng cách thêm số 0 vào n 1b  chuỗi có độ dài n 1 , mà không có hai số 1 liên tiếp . Trường hợp 2: s có chữ số tận cùng là số 1 (và đó là các chuỗi có hai chữ số cuối là 01): Ta có n 2b  chuỗi như vậy, nhận được bằng cách ghép thêm 01 vào n 2b  chuỗi có độ dài n 2 , mà không có hai số 1 liên tiếp . Do đó: n n 1 n 2 0 1b b b , n 2, b 1, b 2,      và số lượng chuỗi nhị phân với độ dài n mà không có hai số 1 liên tiếp là: n n 2 .b F , n 0  Chúng ta xét thêm các kết quả sau đây làm ví dụ: Lấy n = 5 ta có tập con tương ứng với{1, 4} là chuỗi 10010 và tập con tương ứng với {1, 3, 5} là chuỗi 10101. Nói chung, ta sắp xếp các số nguyên trong nS như 1, 2, 3,. . . , n 1, n. Sau đó, cho một dãy của n gồm 0 và 1 (trong đó không có hai số 1 liên tiếp), ta xem xét các vị trí của số 1. Nếu số 1 ở vị trí thứ i, 1 ≤ i ≤ n, sau đó chúng ta chọn i từ nS để xác định tập con tương ứng không có hai số nguyên liên tiếp. 2.4. SỐ LƯỢNG CÁC HOÁN VỊ CỦA nS . Xét tập nS = {1, 2, 3,. . . , n 1, n}, với n ≥ 1. Bây giờ ta xét các hàm f: n nS S là song ánh. Các hàm này được gọi là hoán vị của nS và số các hoán vị là n!. Cho n 1, ta muốn xác định số lượng các hoán vị f thỏa mãn 32 điều kiện | i - f (i) | ≤ 1, với mọi 1 ≤ i ≤ n có nghĩa là, ta muốn tìm số hoán vị f trong đó: (i) f (1) = 1 hoặc f (1) = 2; (ii) f (n) = n hoặc f (n) = n - 1; và, (iii) f (i) = i - 1 hoặc f (i) = i hay f (i) = i + 1 với mọi 2 ≤ i ≤ n - 1. Khi n = 3, ví dụ, trong số sáu hoán vị có thể cho của 3S , ta tìm thấy ba hàm sau thỏa mãn các điều kiện đã cho: 3 3(1) f :S S 3 3(2) f :S S (3) f :S S3 3  f (1) 1 f (1) 1 f (1) 2 f (2) 2 f (2) 3 f (2) 1 f (3) 2 f (3) 2 f (3) 3 Đối với n ≥ 1, ta gọi np là số các hoán vị của nS có đủ các điều kiện đã nêu. Có hai trường hợp xảy ra: (i) f (n) = n: Ở đây chúng ta có thể sử dụng bất kỳ hàm f bị hạn chế bởi n 1S  ; n 1 n 1f :S S .  Suy ra ta có n 1p  các hoán vị . (ii) f (n) = n - 1: Điều này xảy ra khi f (n 1) n,  và với những điều kiện này chúng ta có thể sử dụng bất kỳ hàm f bị hạn chế bởi n 2S  ; n 2 n 2f :S S .  Suy ra ta có n 2p  các hoán vị . Do đó, chúng ta thấy rằng n n 1 n 2 1 2p p p , n 3, p 1, p 2,      và n n 1p F , n 1.  Thang Long University Library 33 2.5. SỐ LƯỢNG CÁC TẬP CON LUÂN PHIÊN CỦA nS . Cho nS = {1, 2, 3, , n - 1, n}, trong đó n ≥ 1, ta xét các tập con của nS có dạng 1 2 3 k{a ,a ,a ,...,a }, trong đó: (i) 1 2 3 ka a a ... a    (với điều kiện k ≤ n); (ii) ia lẻ với i lẻ, i ≤ n; và, (iii) ia chẵn với i chẵn, i ≤ n. Những tập hợp này được gọi là các tập con luân phiên của nS . Khi n = 3, chúng ta tìm thấy năm tập con như vậy cụ thể là, ∅, {1}, {1, 2}, {1, 2, 3}, và {3}. Đối với n = 4, có tám tập con như vậy: ∅, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 4}, {3}, và {3, 4}. Nói chung, đối với n ≥ 1, ký hiệu nt là số các tập con luân phiên của nS . Khi đó 1t 2, 2t 3, và, với n ≥ 3, chúng ta xem xét những điều sau đây: Giả sử 1 2 kB {b ,b ,...,b } là một tập con luân phiên của nS trong đó: (i) 1 2 kb b ... b ;   (ii) ib là lẻ với i lẻ, i ≤ n; và, (iii) ib chẵn với i chẵn, i ≤ n. Có hai trường hợp xảy ra. (1) Nếu 1b 1, thì 2 3 k{b 1,b 1,...,b 1}   là một tập con luân phiên của n 1S . Do đó ta có n 1t  tập con luân phiên của nS có chứa số 1. (2) Nếu 1b 1, thì 1b ≥ 3 và 1 2 k{b 2,b 2,...,b 2}   là một tập con luân phiên của n 2S . Vì vậy, ta có n 2t  tập con luân phiên của nS không chứa số 1. Từ hai trường hợp này ta có số lượng các tập con luân phiên của nS là: n n 1 n 2 1 2t t t , n 3, t 2, t 3,      34 Và khi đó, n n 2t F , n 1.  2.6. SỐ LƯỢNG CÁC TẬP CON BÉO CỦA nS . Cho tập 4S ={1, 2, 3, 4}. Các tập hợp A = {2, 4} là một tập hợp con của 4S và số 2 (phần tử 2 trong tập A) ≥ | A |, kích thước của A. Tương tự như vậy 4 ≥ | A |. Chúng ta gọi một tập hợp con A có tính chất như trên là một tập hợp con béo của 4S . Các tập con B = {3, 4} cũng là một tập hợp con béo của 4S vì số 3 (phần tử 3 trong tập B) ≥ 2 = | B | và 4 ≥ 2 = | B |. Tuy nhiên, các tập con C = {1, 2} không phải là một tập hợp con béo của 4S vì 1 C nhưng 1 2 |C|.  Tổng quát, với n ≥ 1, một tập hợp con A của nS được gọi là một tập hợp con béo của nS nếu x ≥| A | với mọi .x A Có bao nhiêu tập hợp con béo của tập hợp nS bất kỳ? Gọi nf là số lượng các tập con béo của nS , ta thấy rằng với 1S = {1}, cho ta hai tập con béo là ∅ và {1}, khi đó 1f 2, với 2S = {1, 2}, cho ta ba tập con béo là ∅, {1}, và {2}, khi đó 2f = 3. Với n 3, có hai trường hợp cần xem xét. Nếu A là một tập hợp con béo của nS và n A, thì A là một tập hợp con béo của n 1S . Tuy nhiên, nếu n A, thì 1 A bởi vì với 1, n A, thì khi đó | A | 2 và 1 | A|. Sau khi loại bỏ n và trừ đi 1 từ mỗi số nguyên còn lại trong A, chúng ta có được một tập hợp con béo của n 2S . (Ngoài ra, chúng ta có thể lấy bất kỳ tập hợp con béo của n 2S , thêm 1 cho mỗi số nguyên trong bộ này, và sau đó đặt n vào các kết quả mới thiết lập). Do đó, n n 1 n 2 1 2f f f , n 3, f 2, f 3,      Thang Long University Library 35 Thật vậy: Chứng minh. Gọi A là một tập hợp con béo của nS . Ta có.                                    1 1 2 2 3 3 S 1 A 1 , f 2 S 1; 2 A 1 , 2 , f 3 S 1; 2; 3 A 1 , 2 , 3 , 2;3 , f 5                                                                                                                      n n n 2 2 k 0 k 0 n 2 n 1 2 2 k 0 k 0 n n 0 n 1 n 2 n k 1 n f ... ,k 0 1 2 3 k 2 n k 1 n k n k = k k 1 k n k n k k 1 k Suy ra:   n n 2 n 1f f f . □ Ta có: n n 2f F , n 1.  Lưu ý rằng với 4S có tám tập con béo. Điều này cho ta cách xác định số lượng các tập hợp con béo từ 4S = {1, 2, 3, 4}, có một cách để chọn các tập con rỗng, có  41 cách để chọn một tập hợp con béo có kích thước 1, và có  32 cách để chọn một tập hợp con béo có kích thước 2 (từ {2, 3, 4}). Do đó,          4 3 5 4 36 1 2 0 1 2F 1 ,      tổng của các hệ số nhị thức. Tương tự, ta có 7F bằng số các tập con béo của 5S =        6 5 4 30 1 2 3 ,   và với n ≥ 1, ta có cách xác định sau. 36                                        n 1 n 2 n 3 (n 1)/2 0 1 2 (n 1)/2 n n 1 n 2 n 3 n/2 0 1 2 (n/2) 1 ... , n lÎ F ... , n chan 2.7. TẬP CON A CỦA nS CÓ PHẦN TỬ NHỎ NHẤT BẰNG A . Theo cách tương tự, xét ba tập con sau của 10S = {1, 2, 3,. . . , 10} – gồm, {2, 6}, {3, 8, 10}, và {4, 6, 8, 9}. Ta thấy những đặc điểm chung của ba tập con trên. Xét kích thước của mỗi tập con, ta thấy rằng |{2,6}| = kích thước của {2, 6} = 2, phần tử cực tiểu trong {2, 6} |{3,8,10}| = 3, phần tử cực tiểu trong {3, 8, 10} |{4,6,8,9}|= 4, phần tử cực tiểu trong {4, 6, 8, 9}. Vì vậy, với mỗi n ≥ 1, gọi nm là số lượng tập con A của nS trong đó phần tử nhỏ nhất của A bằng | A |, kích thước của A. Để cụ thể hơn chúng ta xét các trường hợp với n = 4, 5 và 6. n = 4: {1}, {2, 3}, {2, 4} n = 5: {1}, {2, 3}, {2, 4}, {2, 5}, {3, 4, 5} n = 6: {1}, {2, 3}, {2, 4}, {2, 5}, {3, 4, 5} {2, 6}, {3, 4, 6}, {3, 5, 6} Năm tập con đầu tiên của n = 6 chính là những trường hợp trong đó n = 5. Nhưng ba tập con cuối cùng của n = 6? Ta đều thấy có số 6 là một phần tử của mỗi tập hợp như vậy, và phần tử cực tiểu nhất là số 2. Trở lại với ba tập con của n = 4, trong mỗi tập hợp con đó chúng ta cộng cho mỗi phần tử 1 đơn vị, và sau đó thêm vào mỗi tập hợp con đó phần tử 6. ( Phần tử lớn nhất có ở trong bất kỳ tập hợp con của 4S là 4, nên không có phần tử k nào trong một tập hợp con của 4S mà k + 1 bị số 6 làm thay đổi. Do đó, {1} trở thành { 1 + 1, 6} = {2, 6} {2, 3} trở thành {2 + 1, 3 + 1, 6} = {3, 4, 6} Thang Long University Library 37 {2, 4} trở thành {2 + 1, 4 + 1, 6} = {3, 5, 6}. Như vậy 56 4m m m .  Lý luận tương tự với mỗi n ≥ 3, ta có công thức truy hồi, n n 1 n 2 1m m m , n 3, m 1     (với {1}), 2m 1 (với {1}). Thật vậy: Chứng minh. Xét tập A có tối thiểu k phần tử.  A k A'   với A' k 1  i i x A' x k 0    Nếu A lấy trong tập N có N n  Số các tập con             n k n A , k 2k 1 với phần tử tối thiểu là k Tập tất cả thỏa mãn đề bài là:                                                                                        n n 2 2 k 1 k 1 n 2 n 1 2 2 k 1 k 1 n n 2 n 1 n k (n 2) (k 1) (n 1) k k 1 k 1 1 k 1 (n 2) (k 1) n 1 k k 1 1 k 1 m m m Do đó, ta có điều phải chứng minh. □ và, khi đó n nm F , với n ≥ 1. Chúng ta cũng đạt được kết quả với n = 7, bằng cách thay thế sau đây, lập luận: (1) Có một tập hợp con khi phần tử cực tiểu là 1, cụ thể là, {1}. (2) Đối với phần tử cực tiểu là 2, ta có  51 tập con, vì ta chọn một trong năm số sau: 3, 4, 5, 6, và 7 là một tập hợp con. 38 (3) Khi phần tử cực tiểu là 3, ta có  42 tập con, vì chúng ta chọn hai số trong bốn số sau: 4, 5, 6, và 7 là một tập hợp con. (4) chỉ có một tập hợp con khi phần tử cực tiểu là 4 - cụ thể là tập con, {4, 5, 6, 7}. Vì vậy, tổng số các tập con của 7S , trong đó phần tử cực tiểu bằng với kích thước của các tập con là: 7 5 54 6 4 3 1 1 13 F . 1 12 0 2 3                                                      Lập luận tương tự ta có công thức tổng quát sau. Với n ≥ 1, thì số tập con A của nS trong đó các phần tử nhỏ nhất của A bằng | A |, kích thước của A là.                                               (n 1)/2n 1 n 2 n 3 0 1 2 (n 1)/2 n n n 1 n 2 n 3 n/2 0 1 2 (n/2) 1 ... , n lÎ m F . ... , n chan Thang Long University Library 39 CHƯƠNG 3: MỘT SỐ BÀI TẬP ÁP DỤNG. Trong chương này, trình bày một số bài toán có liên quan đến kiến thức của chương 1 và chương 2, dựa trên tài liệu tham khảo [1], [2], [3], [4], [5], [6], [7]. Bài tập 1. Với n ≥ 1, chứng minh rằng 2n 2n 12(n 1)F 2F F .   Lời giải: Ta có 2n 2 2n 1 2n 2n 2n 1 2n 2n 2n 12(n 1)F F F F F F F 2F F .            □ Do đó, ta có điều phải chứng minh. Bài tập 2. Với n ≥ 2, chứng minh rằng nn 2 n 2F F 3F .   Lời giải: Ta có n n nn 2 n 2 n 1 n 2 n 1 n 2F F F F F F F F F             n n n nn 1 n 22F (F F ) 2F F 3F .       □ Do đó, ta có điều phải chứng minh. Bài tập 3. Với n ≥ 2, chứng minh rằng n nn 2 n 2F F F 4F .    Lời giải: Ta có n n n n nn 2 n 2 n 1 n 2 n 1 n 2F F F F F F F F F 2F F               n n n nn 1 n 23F (F F ) 3F F 4F .       □ Do đó, ta có điều phải chứng minh. Bài tập 4. Với n ≥ 1, chứng minh rằng 3 3 3n nn 1 n 1 n 1 n 1F F F 3F F F .      Lời giải: Ta có 3 3 3 3n n n nn 1 n 1 n 1 n 1 n 1F (F F ) F F 3F F (F F )          3 3n nn 1 n 1 n 1F F 3F F F .     □ Do đó, ta có điều phải chứng minh. 40 Bài tập 5. Với n ≥ 2, chứng minh rằng 3n 3n 3 3n 6F 4F F .   Giải: Ta có 3n 3n 1 3n 2 3n 2 3n 3 3n 2 3n 2 3n 3F F F F F F 2F F             3n 3 3n 4 3n 3 3n 3 3n 42(F F ) F 3F 2F         3n 3 3n 4 3n 5 3n 63F F F F       3n 3 3n 3 3n 63F F F     3n 3 3n 64F F .   Điều này luôn đúng. □ Do đó ta có 3n 3n 3 3n 6F 4F F .   Bài tập 6. Cho n ≥ 0. Chứng minh rằng m n r m n 2 n 2r 1 F F F .      Giải: Ta sẽ chứng minh bằng phương pháp quy nạp theo m. Với m 1 ta có n 1 n 3 n 2F F F .    Điều này luôn đúng với mọi n N. Giả sử mệnh đề đúng với m k (k 1 N,k )   , tức là: k n r n 2k n 2r 1 F F F .     Ta cần chứng minh mệnh đề đúng với m k 1(k )N1,k    , tức là k 1 n r n 2k n 3r 1 F F F .       Ta có : k 1 k r n r n 2 n 2n k 1 k n 2 n k 1 k n 3n 1 n 1 F F F F F F F F .                     □ Từ đó ta có điều phải chứng minh. Thang Long University Library 41 Bài tập 7. Với n ≥ 1, chứng minh rằng 3 n 1n n 1 n 2 n 1 n 1F F F F F ( 1) .        Giải: Chứng minh 3 n 1 n 1 3n nn 1 n 2 n 1 n 1 n 1 n 2 n 1 n 1F F F F F ( 1) F F F F ( 1) F                 Theo tính chất 1.6.9 ta có. n 1 n 1 2 3 n nn 1 n 2 n 1 n 1 n 2 n 1 n 1 n 1F F F F ( 1) F (F F ( 1) ) F .F F .                 □ Từ đó ta có điều phải chứng minh. Bài tập 8. Sử dụng phương pháp quy nạp toán học để chứng minh rằng với n ≥ 1, n r n1 2 3 n 2 n 3r 1 r F F 2F 3F ... nF nF F 2.          (Công thức này là một ví dụ của một tổng có hệ số bao hàm số Fibonacci .) Giải: Với n 1, ta có n r 1r 1 rF F 1,    n rn 2 n 3 3 4 r 1 nF F 2 F F 2 2 3 2 1 rF .            (luôn đúng) Giả sử mệnh đề đúng với n k(k 1 N),k .   tức là k r 1 2 3 k k 2 k 3r 1 r F F 2F 3F ... kF kF F 2.          (giả thiết quy nạp). Ta cần chứng minh mệnh đề đúng với n k 1.  Hay chứng minh. k 1 r k 3 k 4r 1 rF (k 1)F F 2        Thật vậy: k 1 k r r k 1 k 2 k 3 k 1r 1 r 1 rF rF (k 1)F kF F 2 (k 1)F                k 2 k 1 k 3 k 2 k 3 k 4[(k 1)F (k 1)F ] (F F ) 2 (k 1)F F 2.                □ Từ đó ta có điều phải chứng minh. Bài tập 9. (H. W. Gould, 1963) [2]. Với n ≥ 0, chứng minh rằng 2 2 2 2n n 3 n 1 n 2F F 2(F F ).     42 Giải: Ta có: 2 2 2 2n n 3 n 2 n 1 n 2 n 1F F (F F ) (F F )         2 2 2 2 2 2n 2 n 2 n 1 n 1 n 2 n 2 n 1 n 1 n 2 n 1F 2F F F F 2F F F 2(F F ).                 □ Từ đó ta có điều phải chứng minh. Bài tập 10. Với n ≥ 1, chứng minh rằng 2 2nn 1 n 1 n 2F F F F .    Giải: Ta có : 2 2n n nn 1 n 1 n 1 n 1 n 2F F (F F )(F F ) F F .         (luôn đúng) Ta có điều phải chứng minh. Bài tập 11. (M. N. S. Swamy, 1966) [6]) Với n ≥ 1, chứng minh rằng 2 2 2 2 2n n 4 n 1 n 3 n 2F F F F 4F .       Giải: Ta có 2 2 2 2n n 4 n 2 n 1 n 3 n 2F F (F F ) (F F )         2 2 n 1 n 3 n 3 n 2 n 1 n 2F F 2F F 2F F         2 2 2 n 1 n 3 n 2 n 3 n 1 n 2F F 2F 2(F F )F          2 2 2 2 2 2 2 n 1 n 3 n 2 n 2 n 1 n 3 n 2F F 2F 2F F F 4F             □ Ta có điều phải chứng minh. Bài tập 12. a) Với bất kỳ số thực a và b, chứng minh rằng 2 2 2 2 4 4 4a b (a b) 2 a b (a b) .               [Kết quả này được biết đến cùng với tên của Candido’s , Ông là nhà toán học người Ý Giacomo Candido (1871-1941).] b) Với n ≥ 0, chứng minh rằng 2 2 2 2 4 4 4 n nn 1 n 2 n 1 n 2(F F F ) 2(F F F ).        Thang Long University Library 43 Giải: a) Ta có Vế trái = 2 2 2 2a b (a b)       = 2 2 2 2 2 2[2a 2b 2ab] 4[a b ab]     4 4 2 2 3 3 2 2 4 4 2 2 3 3 4[a b a b 2a b 2ab 2a b a b 3a b] 4[ ]2a b 2ab          4 4 4 4 2 2 3 3 4 4 4a b (a b 6a b 4a b 4a=2[ ] =2[a) ]b b (a b)       = Vế phải. □ Ta có điều phải chứng minh. b) Ta có : Vế trái = 2 2 2 2n n 1 n 2(F F F )   =   2 22 2 n nn 1 n 1F F F F          , vì nn 2 n 1F F F     44 4 n nn 1 n 12 F F F F           4 4 4 n n 1 n 22(F F F ).    = Vế phải. □ Ta có điều phải chứng minh. Bài tập 13. Với n ≥ 0, chứng minh rằng nn 5F 3F  chia hết cho 5. [Ngoài ra, điều này có thể được viết là nn 5F 3F (mod5)].  Lời giải: Chứng minh bằng phương pháp quy nạp toán học. Với n 0, ta có 5 0F 3F 5 3.0 5    chia hết cho 5. (luôn đúng) Giả sử mệnh đề đúng với n k(k 0 N),k .   Tức là k 5 kF 3F  chia hết cho 5, (giả thiết quy nạp) Ta cần chứng minh mệnh đề đúng với n k 1.  Tức là n 6 n 1F 3F  chia hết cho 5. Thật vậy ta có : 44 nn 5n 6 n 1 n 4 n 1F 3F F F 3(F F )        nn 5 n 4 n 1(F 3F ) (F 3F ).      Mà theo giả thiết quy nạp nn 5F 3F  và n 4 n 1F 3F  đều chia hết cho 5 nên nn 5 n 4 n 1(F 3F ) (F 3F ).     chia hết cho 5. Do đó n 6 n 1F 3F  chia hết cho 5. □ Ta có điều phải chứng minh. Bài tập 14. Với n ≥ m ≥ 1, chứng minh rằng n r n 2 m 1.r m F F F    Lời giải: Ta có: n r m m 1 m 2 n n 2 m 1.r m F F F F ... F F F           Chứng minh bằng phương pháp quy nạp toán học. Với n 1, ta có nr m r 1F F 1   và n rn 2 m 1 3 1 1 r m F F F F 2 1 1 F F .          Giả sử mệnh đề đúng với n k(k 1 N),k ,   ta có: k r m m 1 m 1.k k 2r m F F F ... F F F        (giả thiết quy nạp) Ta phải chứng minh mệnh đề đúng với n k 1,  tức là k 1 r m m 1 m 1.k 1 k 3r m F F F ... F F F           Thật vậy ta có: k 1 k r m 1 m 1 m 1k 1 k 2 k 1 k 2 k 1 k 3r m r m F F F F F F F F F F .                      □ Suy ra điều phải chứng minh. Bài tập 15. a) Kiểm tra lại đẳng thức sau 53 4 6 4 8(F F F F ) F F .     b) Với giá trị nào của n thì đẳng thức này đúng: Thang Long University Library 45 n5 7 54 6 8(F F F F F ) F F ?      c) Cho n ≥ 1 và m ≥ 1. Tính giá trị thu gọn của biểu thức sau. n n mn 1 n 2 n 1(F F F ... F ) F ?       (Biểu thức này được công nhận bởi WH Huff.) Lời giải: a) Ta có 5 70 1 2 3 4 6 8F 0,F 1,F 1,F 2,F 3,F 5,F 8,F 13,F 21.         Ta có 53 4 6 4 8(F F F F ) F (2 3 5 8) 3 21 F .           (luôn đúng). b)Ta có 5 7 54 6 8 10(F F F F F ) F (3 5 8 13 21) 5 55 F             Vậy với n 10 thì đẳng thức này đúng. c) Theo kết quả bài 14, ta có n m n n m rn 1 n 2 n 1 n 1 n m 2 n 1 n 1 n m 2r n (F F F ... F ) F F F F F F F                       Vậy :  n n mn 1 n 2 n 1 n m 2F F F ... F F F .          □ Bài tập 16. Với m n 1,  và 1 2F F 1  , chứng minh rằng . n m m nn 1 m 1F F F F F    Lời giải: Chứng minh bằng phương pháp quy nạp toán học theo m. Với m = 1, ta có: Vế trái = n 1F , Vế phải nn 1 1 2F F F F  n,n 1F F  Theo định nghĩa truy hồi ta có: nn 1 n 1F F F ,   ( luôn đúng ). Giả sử mệnh đề đúng với m k(k 1 N),k ,   Tức là : nn 1n k k k 1F F F F F ,   ( giả thiết quy nạp ) Ta phải chứng minh mệnh đề đúng với m k 1,  tức là Chứng minh: nn 1 n 1n k 1 k 2F F F F F     46 Thật vậy ta có. n k 1 n k 1 n kF F F      n nn 1 n 1k 1 k k k 1F F F F F F F F      nn 1 k 1 k k k 1F (F F ) F (F F )      nn 1 k 1 k 2F F F F    □ Vậy n m m nn 1 m 1F F F F F    Bài tập 17. Với m n 1,  chứng minh rằng.  m 2mn 1 n 1 nF F F  Lời giải: Chứng minh bằng phương pháp quy nạp toán học theo m. Với m = 1 ta có: 2n 1 n 1 nF F 0 F   , (luôn đúng). Giả sử mệnh đề đúng với m k(k 1 N),k ,   tức là:  k 2kn 1 n 1 nF F F  , ( giả thiết quy nạp ) Ta phải chứng minh mệnh đề đúng với m k 1,  tức là Chứng minh:   k 1 2 n 1 nk 1 n 1 (F F ) F   thật vậy, theo bài tập 16 ta có:     k 1 k 1 k 1 n 1 kn n 1 n 1 kn 1 n 1 kn n n 1k 1 n 1 F F F F F F F F F                . Theo giả thiết quy nạp, ta có:  k 2kn 1 n 1 nF F mod F  . Do đó:     k 1 k k 1 2 n 1 n 1 n 1 kn n n 1 nk 1 n 1 F F F F F F F modF          Vì kn nF F nên  2kn n nF F 0 mod F Từ đó, ta có:     k 1 2 n 1 nk 1 n 1 F F 0 modF    . □ Thang Long University Library 47 Vậy:  m 2mn 1 n 1 nF F F  Bài tập 18. Với m n 1,  chứng minh rằng.  m m 3mn n 1 n 1 nF F F F   . Lời giải: Chứng minh bằng phương pháp quy nạp toán học theo m. Với m = 1 ta có: 3 n n 1 n 1 n 1 n 1 nF F F F F 0 F        , ( luôn đúng ). Giả sử mệnh đề đúng với m k(k 1 N),k ,   Tức là:  k k 3kn n 1 n 1 nF F F F   , ( giả thiết quy nạp ) Ta phải chứng minh mệnh đề đúng với m k 1,  tức là Chứng minh:  k 1 k 1 3(k 1)n n 1 n 1 nF F F F     Thật vậy, theo bài tập 16 ta có:   k 1 k 1 k 1 k 1 n 1 n 1 kn 1 n kn n 1 n 1 n 1k 1 n F F F F F F F F F               Theo giả thiết quy nạp ta có:  k k 3kn n 1 n 1 nF F F modF   Do đó:   k 1 k 1 k k k 1 k 1 3 n nn 1 n 1 n 1 n 1 n 1 n 1 n 1kn 1k 1 n F F F F F F (F F ) F F (modF )                    k 3kn 1 n n 1 n 1 n 1 nF F F F F modF      hay       k 1 k 1 k 3 n 1 n 1 n kn 1 n 1 nk 1 n F F F F F F modF         Theo bài tập 17 ta có:  k 2kn 1 n 1 nF F F  ,   k 1 k 1 3 n 1 n 1 nk 1 n (F F F ) F     . □ Vậy:  m m 3mn n 1 n 1 nF F F F   48 Bài tập 19. Với m n 1,  và 1 2F F 1  , chứng minh đẳng thức sau . nm n 1 m 1 n m nF F F F ( 1) F .     Chứng minh: Áp dụng (1.2) :   n 1 n nF 1 F     , và n m n 1 m n m 1F F F F F    . Ta có: m n n m n 1 m m 1 n n 2 n 1 m n 1 m 1 n n 2 n 1 m n 1 m 1 n n m n 1 m 1 n F F F F F F F ( 1) F F ( 1) F F ( 1) ( 1) F F ( 1) ( 1) F ( 1) (F F F F )                                 nm n 1 m 1 n m nF F F F ( 1) F .     □ Bài tập 20: Với t 2 và F0 = 0, F1 = F2 = 1. Chứng minh đẳng thức sau:        2 2 2n t t n 1 t 1 n 1 n t 2 n F F .F 2F F F F .F Chứng minh: Ta chứng minh bằng phương pháp quy nạp theo t. + Với t = 2 ta có: Vế trái  2n 2F Vế phải       2 2 n 1 2 1 n 1 n 2 2 n F .F 2F .F F F .F 2 2 2 n 1 1 n 1 n 0 n F .F 2F F F F .F    2 n 1 n 1 n F 2F F    n 1 n 1 nF F 2F    n 1 n 1 n nF F F F       n 1 n 2 nF F F Thang Long University Library 49    n 1 n 2 n n 1F F F F   2n 22 n 1F F    Vế trái = Vế phải , ( đẳng thức luôn đúng ). Giả sử mệnh đề đúng với:    t k, t N,t 2 tức là: 2 2 2n k k n 1 k 1 n 1 n k 2 n F F F 2F F F F F       , (giả thiết quy nạp). Ta phải chứng minh mệnh đề đúng với: t = k + 1 tức là chứng minh: 2 2 2n k 1 k 1 n 1 k n 1 n k 1 n F F F 2F F F F F        Theo giả thiết quy nạp ta có: 2n k 1 2n k 1 2n k F F F      2 2 2 2 k 1 n 1 k 2 n 1 n k 3 n k n 1 k 1 n 1 n k 2 n F F 2F F F F F F F 2F F F F F                    2 2n 1 k 1 k n 1 n k 2 k 1 n k 3 k 2F F F 2F F F F F F F            2 2 k 1 n 1 k n 1 n k 1 n F F 2F F F F F      . □ Điều phải chứng minh. Bài tập 21: Với n 1 chứng minh các đẳng thức:   n3 3 3n n n n 1 n 1 n n F 2F 3F F F 5F 3 1 F      Chứng minh: Theo bài tập 18 với t = n ta có: 2 2 3n 2n n n n 1 n 1 n 1 n n 2 n F F F F 2F F F F F          2 2 n n n 1 n 1 n n 1 n 2 n F F F 2F F F F F       3 2 2 2 n n n 1 n n 1 n 1 n n 1 n 2 n F 2F F F F 2F F F F F          3 2 2 2 2n n n n 2 n n 1 n n 1 n 1 n n 1 n 2 nF F F F F F F F 2F F F F F             3n n 1 n n n 1 n 1 n n 12F F F F F 2F F F       3 n n 1 n n 1 n 1 n n 1 2F F F F 2F F F      50 3 n n 1 n n 1 2F 3F F F   3 3n n n 1 n n 1 F 2F 3F F F    , □ Theo tính chất 1.6.9 ta có:     n n2 2 n 1 n 1 n n 1 n 1 n F F F 1 F F F 1          Do đó: 3 n n 1 n n 1 2F 3F F F    3 n n 1 n 1 n 2F 3 F F F     n3 2 n n n 2F 3F F 1         n3 n n 5F 3F 1     n3 n n 5F 3 1 F   , □ Từ những điều trên ta suy ra:   n3 3 3n n n n 1 n 1 n n F 2F 3F F F 5F 3 1 F      , (điều phải chứng minh). Bài tập 22: Tanya và Greta chia lượt gieo một đồng xu. Tanya đầu tiên, Greta thứ hai, Tanya thứ ba, và như vậy. Họ tiếp tục cho đến khi có kết quả là hai mặt ngửa xuất hiện, lần đầu tiên, trên hai lần gieo liên tiếp thì họ dừng lại. Làm thế nào để biết được, có bao nhiêu dãy kết quả sấp ngửa của trò chơi có thể xảy ra nếu họ dừng chơi sau: (a) bảy lần gieo; (b) n lần gieo, với n ≥ 2? ; (c) 12 lần gieo. Lời giải: a) Gọi S là gieo được kết quả mặt sấp. N là gieo được kết quả mặt ngửa. Và ia là kết quả gieo đồng xu ở lần thứ i. Nếu họ dừng sau 7 lần thì 5 76a a a phải là SNN. Chúng ta nghiên cứu các kết quả của 1 2 3 4a a a a . Thang Long University Library 51 Nếu 4 a là S thì 1 2 3 a a a chỉ cần bỏ đi trường hợp SNN, NNN, NNS thì họ sẽ dừng chơi sau 7 lần gieo. Khi đó số các dãy kết quả sấp ngửa xảy ra nếu họ dừng chơi sau 7 lần gieo là 8 3 5.  Nếu 4a là N thì 3a phải là S chỉ cần xét 2 3a a , khi đó 2 3a a có thể là SS, SN, NS; suy ra có 3 kết quả. Vậy số dãy các kết quả sấp ngửa có thể xảy ra nếu họ dừng gieo sau 7 lần là 8. b) Tương tự như trên. Nếu họ dừng gieo sau 4 lần thì 1 2 3 4a a a a có thể là các dãy .{SSNN,NSNS} Nếu họ dừng gieo sau 5 lần thì 51 2 3 4a a a a a có thể là các dãy .{SNSNN,NSSNN,SSSNN} Nếu họ dừng gieo sau 6 lần thì 51 2 3 4 6a a a a a a có thể là các dãy: .{SSNSNN,SSSSNN,NSNSNN,SNSSNN,NSSSNN} Ta nhận thấy số dãy kết quả sấp ngửa xảy ra, nếu họ dừng gieo sau 6 lần, bằng số dãy kết quả sấp ngửa xảy ra, nếu họ dừng gieo sau 4 lần bằng cách thêm SS ở đầu “{SSNSNN, SSSSNN}”, cộng với số dãy kết quả sấp ngửa xảy ra nếu họ dừng gieo sau 5 lần bằng cách thêm S vào đầu nếu 1a là N “{SNSSNN}” và thêm N vào đầu nếu 1a là S “{NSNSNN, NSSSNN}”. Tương tự, ta nhận thấy số dãy kết quả sấp ngửa xảy ra nếu họ dừng gieo sau n lần bằng số dãy kết quả sấp ngửa xảy ra nếu họ dừng gieo sau n 2 lần viết thêm SS ở đầu “{SSNSNN, SSSSNN}” cộng số dãy kết quả sấp ngửa xảy ra nếu họ dừng gieo sau n 1 lần bằng cách thêm S vào đầu nếu 1a là N và thêm N vào đầu nếu 1a là S. 52 Gọi np là số dãy kết quả sấp ngửa của trò chơi xảy ra khi họ dừng gieo sau n lần. Khi đó, ta có n n 2 n 1p p p .   Dễ nhận thấy n n 1p F . c) Theo như công thức trên. Ta có số dãy kết quả sấp ngửa của trò chơi xảy ra khi họ dừng gieo sau 12 lần là: 12 11p F 89.  Bài tập 23. (a) Cho S = {4, 5,. . . , 16, 17}. Có bao nhiêu tập con của S không chứa hai số nguyên liên tiếp? (b) Cho hai số nguyên dương m, n, và cho T = {m, m + 1, m +2,. . . , m + n - 1, m+ n}. Có bao nhiêu tập con của T không chứa hai số nguyên liên tiếp? (c) Cho U là một tập hợp các số nguyên liên tiếp với phần tử nhỏ nhất là 31. Tìm phần tử lớn nhất trong U nếu số lượng các tập con của U không có hai số nguyên liên tiếp là 55? (d) Giả sử W là một tập hợp các số nguyên liên tiếp với phần tử lớn nhất 7. Nếu W có 377 tập con không chứa hai số nguyên liên tiếp, phần tử nhỏ nhất trong W là gì? Lời giải: Các tập con không chứa hai số nguyên liên tiếp của {4, 5, 6} bao gồm , {4}, {5}, {6}, {4, 6}. Ta nhận thấy số lượng các tập con không chứa hai số nguyên liên tiếp của {3 + 1, 3 + 2, 3 + 3} sẽ bằng số lượng các tập con không chứa hai số nguyên liên tiếp của {1, 2, 3}. Các tập con không chứa hai số nguyên liên tiếp của {4, 5, 6, 7} bao gồm , {4}, {5}, {6}, {7} {4, 6}, {4, 7}, {5, 7}. Tương tự số lượng các tập con không chứa hai số nguyên liên tiếp của tập Thang Long University Library 53 {3 + 1, 3 + 2, 3 + 3, 3 + 4} sẽ bằng số lượng các tập con không chứa hai số nguyên liên tiếp của tập {1, 2, 3, 4}. Theo quy luật đó số lượng các tập con không chứa hai số nguyên liên tiếp của {m, m + 1, m + 2, m + 3, , m + n} sẽ bằng số lượng các tập con không chứa hai số nguyên liên tiếp của tập {1, 2, 3, , n}. Gọi na là số lượng các tập con không chứa hai số nguyên liên tiếp của {m, m + 1, m + 2, m + 3, , m + n}. Khi đó: na là số lượng các tập con không chứa hai số nguyên liên tiếp của tập {1, 2, 3, , n}. Có hai trường hợp có thể xảy ra, và chúng không thể xảy ra đồng thời: Trường hợp 1: Số n không ở trong tập hợp con , khi đó có n 1a  tập con như vậy. Trường hợp 2: Số n ở trong tập con, vì thế không thể có số n 1 trong tập hợp con. Do đó có n 2a  tập con như vậy. Vậy a a a , n 2, a 1, a 2 n n 1 n 2 0 1        Đây là một dãy những con số Fibonacci, nhưng với các điều kiện ban đầu là khác nhau. Ở đây chúng ta có 0 2a 1 F  và 1 3a 2 F .  Do đó, .a F , n 0 n n 2    a) S = {4, 5, 6, , 17} = {3 + 1, 3 + 2, 3 + 3, , 3 + 14} Suy ra số lượng các tập con không chứa hai số nguyên liên tiếp của S là 14 16 .a F 987  b) Ta có tập T = {m, m + 1, m +2,. . . , m + n - 1, m+ n}. với m, n, nguyên dương tùy ý. Do đó, số lượng các tập con không chứa hai số nguyên liên tiếp của T là n n 2.a F  54 c) Ta có U = {31, 32, 33, , ?} = {30 + 1, 30+2, 30+3, , 30 + n} Theo đề bài, ta có n n 2 10a F 55 F .   Do đó .n 2 10 n 8    Vậy phần tử lớn nhất của U là 38. d) Ta có W = {?, , 7} = {m + 1, m+2, m+3, , m + n}. Theo đề bài, ta có n n 2 14a F 377 F n 2 14      n 12 m 7 12 5.      Vậy phần tử nhỏ nhất của U là m+1 = 4. Bài tập 24. Với một số nguyên dương n cố định, ký hiệu na là số các dãy nhị phân n1 2 ,x ,x ,..., x trong đó 1 2 2 3 3 4 4 5x x , x x , x x , x x ,...    và thỏa mãn các điều kiện, (i) n 1 nx x  với n chẵn, trong khi, (ii) n 1 nx x  với n lẻ và lớn hơn 1. Ví dụ, khi n = 4, bao gồm chuỗi 0, 0, 0, 1 theo cách đếm nhưng không phải là thứ tự 1, 0, 0, 1. Xác định na ? . Lời giải: Với n 2, ta có các dãy thỏa mãn là 00, 01, 11. Khi đó: 2 4a 3 F .  Với n 3, ta có các dãy thỏa mãn là 000,010,011,110,111. Khi đó: 3 5a 5 F .  Với n 4, ta có 0001, 0101, 1101, 0000, 0100, 1100, 0111, 1111. 4 6a 8 F .  Với n 5, ta có 00010, 01010, 01110, 11010, 11110, 00011, 01011, 11011, 00000, 01000, 11000, 01111, 11111. 5 7a 13 F .  Ta nhận thấy dãy có số phần tử là chẵn có thể có tận cùng là 01, 11, 00; dãy có số phần tử là lẻ có thể có tận cùng là 10, 11, 00. Thang Long University Library 55 Với n 4 các dãy số được tạo ra bằng cách thêm tận cùng là 01 vào mỗi dãy tương ứng với n 2 , thêm tận cùng là 0 với dãy tương ứng với n 3 có tận cùng là 0 và thêm tận cùng là 1 với dãy tương ứng với n 3 có tận cùng là 1; Khi đó, 4 3 2a a a .  Tương tự với n 5, ta nhận được các dãy số bằng bằng cách thêm tận cùng 10 vào các dãy tương ứng với n 3, thêm tận cùng là 0 với dãy tương ứng với n 4 có tận cùng là 0, và thêm tận cùng là 1 với dãy tương ứng với n 4 có tận cùng là 1. Khi đó, 5 4 3a a a .  Tổng quát số dãy có độ dài n k có hai trường hợp: Trường hợp 1: với k là số chẵn. Ta có các dãy số được tạo ra bằng cách thêm tận cùng là 01 vào mỗi dãy tương ứng với n k 2  , thêm tận cùng là 0 với dãy tương ứng với n k 1  có tận cùng là 0 và thêm tận cùng là 1 với dãy tương ứng với n k 1  có tận cùng là 1. Ta có: k k 1 k 2a a a .   Trường hợp 2: với k là số lẻ. Ta có các dãy số được tạo ra bằng cách thêm tận cùng là 10 vào mỗi dãy tương ứng với n k 2  , thêm tận cùng là 0 với dãy tương ứng với n k 1  có tận cùng là 0 và thêm tận cùng là 1 với dãy tương ứng với n k 1  có tận cùng là 1. Ta có: k k 1 k 2a a a .   Do đó ta có n n 1 n 2 n 2a a a F .     Là số Fibonacci. Bài tập 25. Lan và Hoa có bộ sưu tập khối xếp hình, đáy của mỗi khối là hình vuông cạnh 3 inches. Chiều cao mỗi khối là 1 inch hoặc 2 inches, số lượng các khối 56 không hạn chế. Lan và Hoa xếp tòa tháp khối này chồng lên khối kia. Có bao nhiêu cách xếp tòa tháp cao: a) n inches.? b) 10 inches.? c) 17 inches.? Lời giải: a) n inches. Gọi số cách xếp là tòa tháp cao n inches là Fn .  Với n=1 . Tháp cao 1 inch có 1 cách xếp. ta có 1F 1 .  Với n=2 . Tháp cao 2 inches có 2 cách xếp. ta có 2F 2 .  Với n=3 . Tháp cao 3 inches có 3 cách xếp. ta có 3F 3 . (Suy đoán 3 = 2 + 1). Giả sử tòa tháp cao n inches ta có hai trường hợp. -Trường hợp 1: Hộp cuối cùng cao 1 inch, ta có n-1 tầng còn lại. Khi đó có n 1F  cách xếp. -Trường hợp 2: Hộp cuối cùng cao 2 inches, ta có n-2 tầng còn lại. Khi đó có n 2F  cách xếp. Suy ra n n 1 n 2F F F   . (Nếu giả sử 0F 1 thì n n 1 n 2F F F   là số Fibonacci thứ n+1). b) Tòa tháp cao 10 inches. Ta có n 10 . Đây là số Fibonacci thứ 11 11F 89  . c) Tòa tháp cao 17 inches. Ta có n 17 . Đây là số Fibonacci thứ 18 18F 2584  . Bài tập 26. Sinh nhật Hồng nhận được một thùng gồm 40 khối vuông kích cỡ 2 inches : 20 khối màu đỏ (Đ) ,20 khối màu trắng (T) . Hồng muốn xếp các Thang Long University Library 57 khối liền nhau, ta mã hóa như sau. Ký hiệu S là một chuỗi n ký tự Đ và T và được chia thành k khúc (1 k 40)  , khúc là đoạn dài nhất cùng màu. Ví dụ có 8 hộp xếp là ĐTĐĐTTTĐ có 5 khúc Đ, T, ĐĐ, TTT, và Đ. Hồng thích thú khi muốn đếm xem có bao nhiêu cách xếp, khi xếp 10 khối bắt đầu bằng Đ. Các khúc sau phải có độ dài là lẻ. (Khúc đầu chỉ có Đ) độ dài 1. Bài giải. Vấn đề ở đây là n khối chứ không phải là 10 khối. Cụ thể ta gọi nF là số cách xếp n khối. + Nếu xếp hai khối ĐT thì chỉ có một cách xếp. Ta có 1F 1 . +) Nếu xếp ba khối ĐTĐ thì cũng chỉ có một cách xếp. Ta có 2F 1 . +) Nếu xếp bốn khối: ĐTTT hoặc ĐTĐT ( vì khúc đầu là Đ và có độ dài 1). Do đó có hai cách xếp. Nên 4F 2 . Ta thấy: 4F nhận được bằng cách thêm tận cùng bằng TT vào dãy tương ứng của 2F , thêm tận cùng bằng T vào dãy tương ứng của 3F . Khi đó: 4 3 2F F F  . Tổng quát : Ta có số cách xếp nF ?. Vì hộp đầu tiên phải là màu đỏ nên có hai trường hợp: +) Trường hợp 1: Hộp cuối cùng thuộc khúc có độ dài lớn hơn 1 ta thêm 2 hộp cùng màu với hộp cuối thì mới tạo ra khúc độ dài lẻ. Do đó có n 2F  cách. +) Trường hợp 2: Hộp cuối thuộc khúc có độ dài 1, ta thêm một hộp khác màu thì mới tạo ra khúc độ dài lẻ (= 1). Do đó có n 1F  cách. Mặt khác cách thêm n > 2 hộp lại nằm trong các trường hợp trên. Vậy n n 1 n 2F F F   . Đây là số Fibonacci. 58 KẾT LUẬN. Tôi đã đọc và trình bày lại một số kết quả nghiên cứu về, một số đồng nhất thức của số Fibonacci và ứng dụng. Cụ thể : 1. Trình bày tiểu sử nhà toán học Fibonacci, cùng bài toán các cặp thỏ, định nghĩa truy hồi, dựa trên tài liệu tham khảo [1]. Bằng cách phát triển từ công thức truy hồi, tác giả của [1] đã chứng minh một số đồng nhất thức của số Fibonacci một cách đơn giản, dễ hiểu. Cách tiếp cận này cho phép tác giả có được các tính chất đại số và số học đẹp của dãy số Fibonacci. 2. Trình bày một số kết quả nghiên cứu về ứng dụng của dãy số Fibonacci, dựa trên chương 5 trong tài liệu tham khảo [1]. Cụ thể đối với các ví dụ tìm số lượng các tập con của nS có các tính chất riêng biệt. 3. Trình bày được sự tồn tại, và xuất hiện đa dạng của dãy số Fibonacci trong các bài tập áp dụng. Tuy nhiên, việc vận dụng thành thạo các kiến thức nói trên để giải các bài tập về dãy số truy hồi vẫn đang là vấn đề được quan tâm. Thang Long University Library 59 TÀI LIỆU THAM KHẢO [1] Grimaldi, Ralph. Fibonacci and Catalan Numbers: an introduction. John Wiley & Sons, 2012. [2] Gould, Henry W. Problem B - 7. The Fibonacci Quarterly, Volume 1, Issue 3, October, 1963. P. 80. [3] Grimaldi, Ralph P. Generating Sets and the Fibonacci Numbers, Congressus Numerantium, Volume 110, 1995, Pp. 129 – 136. [4] Koshy, Thomas. Fibonacci and Lucas Numbers with Applications. New York: John Wiley & Sons, Inc., 2001. [5] Sloane. Neil James Alexander. The On-Line Encyclopedia of Integer Sequences [6] Swamy, M. N. S. Problem B - 83. The Fibonacci Quarterly, Volume 4, Issue 4, December, 1966, P. 375. [7] Tanton, James S. Fibonacci Numbers. Generating Sets, and Hexagonal Properties. The Fibonacci Quarterly, Volume 38, Issue 4, August, 2000, Pp. 299 – 309. CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc GIẤY XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn: Đỗ Thị Hương Đề tài luận văn: MỘT SỐ ĐỒNG NHẤT THỨC CỦA SỐ FIBONACCI VÀ ỨNG DỤNG Ngành: Toán và Thống Kê Chuyên ngành: Phương pháp toán sơ cấp. Mã Học viên: C00268 Cơ sở đào tạo: Trường Đại học Thăng Long Căn cứ vào biên bản cuộc họp Hội đồng chấm luận văn thạc sĩ ngày 07/06/2016 tại Trường Đại học Thăng Long và các nhận xét, góp ý cụ thể của các thành viên hội đồng, tác giả luận văn đã thực hiện các chỉnh sửa sau: 1. Chỉnh sửa mục 1.5. 2. Chỉnh lại một số câu cụt, thừa chữ hoặc thiếu chữ trong trình bày. Hà nội, ngày 10 tháng 07 năm 2016 Xác nhận của giáo viên hướng dẫn Tác giả luận văn Đỗ Thị Hương Xác nhận của Chủ tịch Hội đồng chấm luận văn Thang Long University Library