Tài liệu Việc biểu diễn một số tự nhiên thành tổng của các số fibonacci tổng quát

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ TRĂNG VIỆC BIỂU DIỄN MỘT SỐ TỰ NHIÊN THÀNH TỔNG CỦA CÁC SỐ FIBONACCI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ TRĂNG VIỆC BIỂU DIỄN MỘT SỐ TỰ NHIÊN THÀNH TỔNG CỦA CÁC SỐ FIBONACCI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NÔNG QUỐC CHINH Thái Nguyên - 2017 i Mục lục Danh sách kí hiệu ii Mở đầu 1 Chương 1. Về dãy số Fibonacci 3 1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Các tính chất của dãy số Fibonacci . . . . . . . . . . . . . . . . . . . . . 5 1.3 Về Định lí Zeckendorf . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Một số bài toán sơ cấp ứng dụng về dãy số Fibonacci . . . . . . . . . . . 9 Chương 2. Biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát 13 2.1 Biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt . . . . 13 2.2 Biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát . . . 23 Kết luận 34 Tài liệu tham khảo 35 ii Danh sách kí hiệu {. . .} là dãy số nguyên (. . .) là một vector có các tọa độ nguyên. [. . .] là các ma trận mà phần tử là các số nguyên. V là tập hợp bao gồm các vector có dạng (i1 , i2 , . . . , id ) với d > 1, các thành phần iν là các số nguyên với 1 ≤ i1 ≤ i2 ≤ . . . id . Thông thường ta sẽ viết I thay cho (i1 , i2 , . . . , id ). n
k M m ∑ bi i=1 ∞ ∑ bn n=1 tổ hợp chập k của n là ma trận [uµ , ν]. m (tổng hữu hạn) ∑ bi = b1 + b2 + · · · + bm i=1 ∞ (chuỗi vô hạn) ∑ bn = b1 + b2 + · · · + bn + · · · n=1 1 Mở đầu Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Dãy số Fibonacci tuy rất đơn giản về quy tắc thiết lập nhưng là một trong những vẻ đẹp đặc biệt trong kho tàng Toán học. Dãy số Fibonacci vô cùng biến hóa với nhiều tính chất lí thú và ứng dụng quan trọng. Người ta đã tìm thấy rất nhiều vấn đề thú vị liên quan đến dãy số Fibonacci, cả ở toán học thuần túy đến những vấn đề khác trong tự nhiên. Dãy Fibonacci được đưa ra bởi nhà toán học Ý tên là Leonardo Pisano Bogollo (tên thường gọi là Fibonacci) vào thời gian khoảng năm 1170 đến năm 1250. Dãy số Fibonacci bí ẩn và lí thú đến mức, đã có một tạp chí toán học hoàn toàn chỉ đăng các kết quả nghiên cứu có liên quan nó, đó là tạp chí The Fibonacci Quarterly. Mục tiêu của luận văn là nghiên cứu một sự kiện thú vị về dãy Fibonacci, đó là việc biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát. Nội dung của luận văn được trình bày trong hai chương: • Chương 1. Số Fibonacci. Trong chương này trình bày các định nghĩa và các tính chất cơ bản của các dãy số Fibonacci. Một số bài toán sơ cấp ứng dụng về dãy số Fibonacci 2 • Chương 2. Việc biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát. Mở rộng định lí Zeckendorf và biểu diễn số tự nhiên bằng các số Fibinacci phân biệt. Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của PGS.TS. Nông Quốc Chinh. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và hoàn thành khóa học. Thái Nguyên, ngày 10 tháng 11 năm 2017 Tác giả Nguyễn Thị Trăng 3 Chương 1 Về dãy số Fibonacci 1.1 Định nghĩa và ví dụ Định nghĩa 1.1.1. Dãy số Fibonacci là dãy số vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng của hai phần tử trước nó, un+1 = un + un−1 Ví dụ 1.1.2. Fibonacci lần đầu tiên để ý đến dãy số trên khi ông xét một bài toán về thỏ đẻ con như sau : Bắt đầu với một thỏ đực và thỏ cái, hỏi có bao nhiêu cặp thỏ có thể được sinh ra trong một năm? Bài toán giả sử với những điều kiện sau: 1. Bắt đầu với một thỏ đực và thỏ cái vừa chào đời. 2. Thỏ đạt tới tuổi thuần thục sinh sản sau một tháng. 3. Thời gian mang thai thỏ là một tháng. 4. Sau khi thuần thục sinh sản, thỏ cái đẻ đều mỗi tháng. 5. Một thỏ cái sinh ra một thỏ đực và một thỏ cái. 6. Không có thỏ chết. 4 Từ giả thiết suy ra rằng, từ cặp thỏ sơ sinh sau hai tháng sẽ có hai cặp thỏ. Sau ba tháng, cặp thứ nhất sinh ra một cặp nữa, và ta có ba cặp. Tháng tiếp theo, cặp thứ hai cũng sinh ra cặp mới, và ta có 5 cặp thỏ. Kí hiệu qua u(n) số cặp thỏ sau tháng thứ n kể từ đầu năm. Ta thấy sau tháng (n + 1) thì sẽ có u(n) cặp ban đầu, cộng thêm số cặp do các cặp đã có sau tháng thứ (n − 1) sinh ra. Số này là u(n − 1). Vậy u(1) = 1, u(2) = 1, u(3) = 2, (1.1) u(4) = 3, ..., u(n + 1) = u(n) + u(n − 1). Theo giả thiết, u(1) = 1, u(2) = 1, nên ta có u(3) = 2, u(4) = 3, . . . , u(12) = 144, u(13) = 233. Các số u(n) được gọi là các số Fibonacci. Xét dãy Fibonacci xác định bởi u(n + 1) = u(n) + u(n − 1). Phương trình đặc trưng của quan hệ (1.1) là r2 − r − 1 = 0. Phương trình này có các nghiệm √ 1+ 5 r1 = , 2 và √ 1− 5 r2 = . 2 (1.2) 5 Nghiệm tổng quát của quan hệ (1.1) có dạng: √ !n √ !n 1+ 5 1− 5 u(n) = C1 +C2 . 2 2 (1.3) Các số Fibonacci u(n) được cho bởi (1.3) với điều kiện u(0) = 1, u(1) = 1. Khi đó các hằng số C1 , C2 được tính từ hệ phương trình.   C +C = 0 1 2 √  5 (C −C ) = 1. 2 Giải ra ta được C1 = √1 5 1 2 và C2 = − √1 .Vậy nghiệm tổng quát có dạng 5  u(n) = √ n  √ n 1+ 5 − 1−2 5 2 √ 5 . Công thức trên đây được gọi là công thức Binet. Dựa vào công thức Binet, ta có định lí sau đây cho một tính chất thú vị của các số Fibonacci. 1.2 Các tính chất của dãy số Fibonacci  √ n 1 Định lí 1.2.1. Số Fibonacci un là số nguyên gần nhất đối với số √ 1+2 5 , 5  √  1+ 5 1 tức là số hạng an của cấp số nhân với từ đầu tiên là √ và công 2 5 √ bội là 1+2 5 . Chứng minh. Rõ ràng chỉ cần chứng minh rằng trị tuyệt đối của hiệu giữa hai số un và an luôn luôn bé hơn 1/2. Ta có  n   n  n  n − rn   r1 − r2n  r r − r |r2 |n 1 1 2 1     √ |un − an | =  √ − √  =   = √5 . 5 5 5 Do nên |un − an | < 21 .    1 − √5  3 − 1   |r2 | =  √  < =1  2 5  6 Sau đây ta sẽ chứng minh một số tính chất cơ bản của dãy số Fibonacci. Trong các mệnh đề sau đây, un dùng để kí hiệu số Fibonacci thứ n xác định bằng u1 = 0, u2 = 1, un+1 = un + un−1 . Mệnh đề 1.2.2. u1 + u2 + . . . + un = un+2 − 1. Chứng minh. Ta có u1 = u3 − u2 , u2 = u4 − u3 , ... un−1 = un+1 − un , un = un+2 − un+1 . Cộng từng vế đẳng thức này, ta có u1 + u2 + . . . + un = un + 2 − u2 , mà u2 = 1 nên ta có điều phải chứng minh. Mệnh đề 1.2.3. u1 + u3 + u5 + . . . + u2n−1 = u2n . Chứng minh. Ta có u1 = u2 , u3 = u4 − u2 , u5 = u6 − u4 , ... (1.4) 7 u2n−3 = u2n−2 − u2n−1 , u2n−1 = u2n − u2n−2 . Cộng từng vế các bất đẳng thức, ta được u1 + u3 + u5 + . . . + u2n−1 = u2n . Ta có điều phải chứng minh. Mệnh đề 1.2.4. u2 + u4 + . . . + u2n = u2n+1 − 1. Chứng minh. Từ Mệnh đề 1.2.2 ta có u1 + u2 + u3 + . . . + u2n = u2n+2 − 1. Từ Mệnh đề 1.2.3 ta có u1 + u3 + u5 + . . . + u2n−1 = u2n . Trừ từng vế đẳng thức này ta được u2 + u4 + . . . + u2n = u2n+2 − 1 − u2n = u2n+1 − 1. Điều phải chứng minh. Mệnh đề 1.2.5. u1 − u2 + u3 − u4 + . . . + (−1)n+1 un = (−1)n+1 un−1 + 1. Chứng minh. Từ các Mệnh đề 1.2.3 và Mệnh đề 1.2.4 ta được u1 − u2 + u3 − u4 + . . . + u2n−1 − u2n = u2n − u2n−1 + 1. (1.5) Cộng thêm vào hai vế u2n+1 ta có u1 − u2 + u3 − u4 + . . . − u2n + u2n+1 = u2n + 1. (1.6) Công thức trong Mệnh đề 1.2.5 chính là kết hợp của hai công thức (1.5) và (1.6) (tương ứng với n lẻ và n chẵn). 8 Mệnh đề 1.2.6. u21 + u22 + . . . + u2n = un un+1 . Chứng minh. Ta có uk uk+1 − uk−1 uk = uk (uk+1 − uk−1 ) = u2k . Do đó, u21 = u1 u2 , u22 = u2 u3 − u1 u2 , u23 = u3 u4 = u2 u3 , ..., u2n = un un+1 − un−1 un . Cộng từng vế các đẳng thức này, ta được u21 + u22 + . . . + u2n = un un+1 . 1.3 Về Định lí Zeckendorf Bổ đề 1.3.1. Giả sử dãy số (ci )i=0,1,...,k là dãy tăng, thỏa mãn ci > 2 và ci+1 > ci + 1 với mọi i = 0, 1, . . .. Khi đó ta có k ∑ uc i < uck +1 i=1 Định lí 1.3.2 (Zeckendorf). Xét N là số nguyên dương bất kỳ. Khi đó tồn tại duy nhất dãy số (ik )i=1,2,...,d tăng, thỏa mãn ik > 1 và ik+1 > ik + 1 với mọi k = 1, 2, . . . , d − 1 có biểu diễn sau N = ui1 + ui2 + · · · + uid (1.7) Đẳng thức (1.7) được gọi là biểu diễn Zeckendorf cho số nguyên dương n. 9 1.4 Một số bài toán sơ cấp ứng dụng về dãy số Fibonacci Mục này sẽ trình bày một số bài toán sơ cấp ứng dụng về dãy số Fibonacci. Bài toán 1.4.1. Giả sử uk là số hạng thứ k của dãy Fibonacci. Chứng minh rằng với mọi số tự nhiên n ≥ 3, thì số An = 4un−2 un un+2 un+4 + 9 là một số chính phương. Lời giải. Trước hết ta có nhận xét sau đây: Với mọi số Vn = |un+4 un−2 − un+2 un | = 3. (1.8) Thật vậy Vn = |(un+2 + un+3 )un−2 − un+2 | = |un+3 + un−2 + un+2 (un−2 un )| = |un+3 + un−2 + un+2 + un−1 | = |un+3 + un−2 + un+2 (un−2 un )| = |un+3 + un−2 + un+2 + un−1 | = |un+3 (un−1 − un−3 ) − un+2 un−1 | = |un+3 + un+1 (un+2 − un+3 )| = |un+3 un−3 − un+1 un−1 | = Vn−1 . Từ Vn = Vn−1 , và quá trình ấy cứ lặp lại, ta đi đến Vn = V3 , với mọi n ≥ 3. (1.9) Ta có V3 = |u7 u1 − u5 u3 | = |13 · 1 − 15 · 2| = 3 như thế nhận xét (1.8) được chứng minh. Từ (1.8) suy ra un+4 un−2 = un un+2 ± 3 hay An = 4un un+2 (un un+2 ± 3) + 9 = (2un un+2 ± 3)2 . 10 Do un nguyên với mọi n ∈ N suy ra An là số chính phương với mọi n ≥ 3 nguyên. Ta có điều cần chứng minh. Bài toán 1.4.2. Chứng minh rằng mọi số tự nhiên thì hoặc là một số Fibonacci, hoặc có thể biểu diễn thành dạng của tổng một vài số Fibonacci phân biệt, ở đây ta hiểu số Fibonacci là một phần tử của dãy Fibonacci. Lời giải. Kí hiệu uk là số Fibonacci thứ k với k ∈ N. Xét dãy Fibonacci 1, 1, 2, 3, 4, 8, 13, . . . Ta chứng minh điều khẳng định của bài toán bằng nguyên lí quy nạp toán học. Với n = 1, 2, 3, 4 (và để ý rằng 4 = 3 + 1, ta thấy điều khẳng định của bài toán đã đúng với mọi số tự nhiên nhỏ hơn u5 = 5). Giả sử điều khẳng định của bài toán đã đúng với mọi số tự nhiên n nhỏ hơn uk . Khi đó dĩ nhiên khẳng định của bài toán cũng đúng khi n = uk . Xét các số tự nhiên n mà uk < n < uk+1 . (1.10) uk+1 = uk + uk−1 . (1.11) Chú ý rằng ta có Từ (1.10) và (1.11) sy ra các số n thoả mãn (1.10) có thể biểu diễn dưới dạng: n = uk + m, 0 < m < uk−1 . (1.12) Từ (1.12) và giả thiết quy nạp suy ra mọi số tự nhiên m nhỏ hơn uk − 1 có thể biểu diễn thành tổng của một vài số Fibonacci khác nhau, chỉ số của các số này nhỏ hơn k − 1. Vì thế số n = uk + m cũng có thể biểu diễn được thành tổng của các số Fibonacci (trong các số đó, số lớn nhất thì bằng uk còn các sô khác có các chữ số nhỏ hơn k − 1). Vậy điều khẳng định của bài toán cũng đúng với mọi số tự nhiên n nhỏ hơn uk + 1. 11 Theo nguyên lí quy nạp toán học, ta suy ra điều khẳng định của bài toán cũng đúng với mọi số tự nhiên. Bài toán được chứng minh. Bài toán 1.4.3. Chứng minh rằng không có 8 số Fibonacci liên tiếp có tổng là một số Fibonacci. Lời giải. Xét tổng Sk = uk+1 + uk+2 + uk+3 + . . . + uk+8 của 8 số Fibonacci liên tiếp. Chú ý rằng với dãy Fibonacci ta có: u1 ≤ u2 < u3 < u4 < . . . < un < . . . Vì dãy Fibonacci là tăng thực sự kể từ u2 , nên nếu ta chứng minh được với mọi k tự nhiên mà uk+9 < Sk < uk+10, thì rõ ràng Sk không phải là một số Fibonacci, và từ đó suy ra kết luận của bài toán là đúng. Thật vậy, ta có uk+9 + uk+9 + uk+7 < uk+8 + uk+7 + uk+6 + . . . + uk+1 = Sk (vì mọi số hạng của dãy Fibonacci đều dương). Bây giờ ta chỉ còn phải chứng minh rằng Sk < uk+10. . Ta có nhận xét sau đây: “Nếu gọi Sn là tổng của n số Fibonacci đầu tiên, thì với mọi n ≥ 2 ta có Sn + 1 = un+2 . (1.13) Công thức (1.13) được chứng minh bằng quy nạp như sau • Với n = 2, ta có S2 = 1 + 1 nên S2 + 1 = 3 = u4 . Vậy (1.13) đúng khi n = 2. 12 • Giả sử khẳng định (1.13) đã đúng với k = n, tức là Sk = u1 + u2 + . . . + uk + 1 = uk+2 . (1.14) • Xét khi n = k + 1. Ta có Sk+1 +1 = u1 +u2 +. . .+uk +uk+1 +1 = (u1 +u2 +. . .+uk +1)+uk+1 . Từ giả thiết quy nạp (1.14) suy ra Sk+1 + 1 = uk+2 + uk+1 = uk+3 . Vậy (1.13) cũng đúng khi n = k + 1. Theo nguyên lí quy nạp toán học suy ra (1.13) đúng với mọi n ≥ 2. Trở lại bài toán đang xét, ta có Sk = uk+1 + uk+1 + . . . + uk+8 = Sk+8 − Sk . Theo nhận xét trên suy ra Sk = (uk+10 − 1) − (uk+2 − 1) = uk+10 − uk+2 < uk+10 do uk+2 > 0. Vậy bất đẳng thức uk+9 < Sk < uk+10 đã được chứng minh. Bài toán được giải hoàn toàn. Bài toán 1.4.4. Chứng minh rằng mọi số nguyên dương N có thể được viết thành tổng các số rời rạc không liên tiếp của dãy số Fibonacci. Lời giải. Giả sử (un )n≥1 là dãy số Fibonacci. Khi đó u1 = u2 = 1 và un+2 = un+1 + un với mọi n ≥ 1. Ta giả sử rằng un ≤ N < un+1 . Do vậy, 0 ≤ N − un < un − 1. Khi đó tồn tại s < n − 1 sao cho us ≤ N − un < us+1 . Do đó 0 ≤ N − un − us < us−1 và s − 1 < n − 2. Do đó N có thể được viết thành N = un + us + u p + . . . + ur , trong đó các n, s, p, . . . , r là chỉ số của các số không liên tiếp. 13 Chương 2 Biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát Chương này sẽ trình bày về biểu diễn số tự nhiên bằng các số Fibonacci phân biệt và biểu diễn số tự nhiên bằng các số Fibonacci tổng quát. Như định nghĩa dãy số Fibonacci trong Định nghĩa 1.1.1 trong chương 1. Ta xét dãy số Fibonacci (un ) với   u1 = 1, u2 = 2;  un = un−1 + un−2 2.1 (2.1) với n > 3. Biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt Mục này trình bày về việc biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt. Nội dung của mục này sẽ được trình bày theo bài báo của H.H. Ferns (xem [4]). Trước tiên ta xét ví dụ sau: Ví dụ 2.1.1. Xét số nguyên 29. Nó có thể được khai triển thành tổng của các số Fibonacci theo cách sau đây: 29 = u8 + u6 = u8 + u5 + u4 14 = u8 + u5 + u3 + u2 = u7 + u6 + u5 + u4 = u7 + u6 + u5 + u3 + u2 . Từ Ví dụ 2.1.1 này, ta thấy rằng cần phải áp đặt một số “quy tắc cơ bản” nếu chúng ta phân biệt giữa các loại biểu diễn khác nhau. Ta có một số định nhĩa sau. Định nghĩa 2.1.2. Một biểu diễn được gọi là • tối tiểu nếu nó không chứa hai số Fibonacci liên tiếp; • tối đại nếu không có hai số Fibonacci liên tiếp ui và ui+1 được bỏ qua trong biểu diễn, trong đó u2 6 ui < ui+1 6 un và un là số Fibonacci lớn nhất được chứa trong biểu diễn. Như vậy, u8 + u6 là một biểu diễn tối tiểu của số nguyên 29 trong khi đó u7 + u6 + u5 + u3 + u2 là một biểu diễn tối đại. Từ đây ta có một biểu diễn tối đại (tương ứng, biểu diễn tối tiểu) có thể được biến đổi vào một biểu diễn tối tiểu (tương ứng, biểu diễn tối đại) bằng cách áp dụng công thức truy hồi của dãy số Fibonacci. Như một ví dụ minh họa của các biểu diễn tối tiểu, ta xét các biểu diễn của tất cả các số nguyên N thỏa mãn u7 6 N < u8 . Khi đó N có thể là một trong tám số 13, 14, 15, 16, 17, 18, 19 hoặc 20. Số nguyên nhỏ nhất trong tập hợp này là 13, không thể được biểu diễn bởi các số Fibonacci u2 , u3 , u4 , u5 và u6 , do số nguyên lớn nhất dưới quy tắc biểu diễn tối tiểu mà đó là quy tắc biểu diễn, u6 + u4 + u2 = 12. 15 Do đó để biểu diễn tất cả các số nguyên của tập hợp này đòi hỏi u2 , u3 , u4 , u5 , u6 và u7 . Bằng các kiểm tra thử, ta có các biểu diễn sau 13 = u7 ; 14 = u7 + u2 ; 15 = u7 + u3 ; 16 = u7 + u4 ; 17 = u7 + u4 + u2 ; 18 = u7 + u5 ; 19 = u7 + u5 + u2 ; 20 = u7 + u5 + u3 . Một trong những số nguyên này là 13, chỉ một số Fibonacci để biểu diễn nó. Bốn số 14, 15, 16 và 18 đòi hỏi hai số Fibonacci và ba số 17, 19, và 20 cần ba số Fibonacci để biểu diễn. Định nghĩa 2.1.3. Số Un,m là ký hiệu số các số nguyên N trong miền un 6 N < un+1 mà cần m số Fibonacci để biểu diễn. Từ định nghĩa ta có U7,1 = 1; U7,2 = 4; U7,3 = 3. Rõ ràng là U7,1 +U7,2 +U7,3 = u8 − u7 = u6 = 8. Từ (2.1) ta có Un,m = 0 nếu m> hni 2 . 16 Do đó, ta có n ∑ Un,i = un+1 − un = un−1. i=1 Bảng 2.1 xác định các giá trị của Un,m với n = 1, 2, 3, . . . , 8 và m = 1, 2, 3, . . . , 4. m n 1 2 3 4 u1 6 N < u2 1 0 0 0 0 u2 6 N < u3 2 1 0 0 0 u3 6 N < u4 3 1 0 0 0 u4 6 N < u5 4 1 1 0 0 u5 6 N < u6 5 1 2 0 0 u6 6 N < u7 6 1 3 1 0 u7 6 N < u8 7 1 4 3 0 u8 6 N < u9 8 1 5 6 1 Bảng 2.1: Giá trị của Un,m n = 1, 2, . . . , 8 với m = 1, 2, . . . , 4. Bây giờ ta xét một số tính chất của hàm Un,m . Xét các số nguyên P, Q và R được xác định bởi các quan hệ sau đây un 6 P < un+1 ; un−1 6 Q < un ; un−2 6 R < un−1 . Do đó P = un + p, Q = un−1 + q, R = un−2 + r, p = 0, 1, 2, . . . , un−1 − 1, q = 0, 1, 2, . . . , un−2 − 1, r = 0, 1, 2, . . . , un−3 − 1. Sắp xếp các số nguyên P trong hai tập hợp (A) và (B) như sau: (2.2) (2.3) (2.4)