Tài liệu Về tính chia hết của các số fibonacci suy rộng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN QUYÊN VỀ TÍNH CHIA HẾT CỦA CÁC SỐ FIBONACCI SUY RỘNG 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 VĂN QUYÊN VỀ TÍNH CHIA HẾT CỦA CÁC SỐ FIBONACCI SUY RỘNG 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 TS. NGÔ VĂN ĐỊNH Thái Nguyên - 2017 Mục lục Lời cảm ơn ii Mở đầu 1 Chương 1 . Dãy Fibonacci suy rộng 3 1.1 Phương trình sai phân tuyến tính cấp 2 . . . . . . . . . 3 1.2 Định nghĩa dãy Fibonacci suy rộng . . . . . . . . . . . 6 1.3 Một số tính chất của dãy Fibonacci suy rộng . . . . . . 7 Chương 2 . Tính chia hết của các số Fibonacci suy rộng 14 2.1 Kết quả của Hoggatt và Long . . . . . . . . . . . . . . 14 2.2 Kết quả của Aoki và Sakai . . . . . . . . . . . . . . . 18 2.3 So sánh với kết quả của Kôzaki và Nakahara . . . . . . 33 Kết luận 37 Tài liệu tham khảo 38 i Lời cảm ơn Luận văn được hoàn thành tại trường Đại học Khoa Học - Đại học Thái Nguyên dưới sự hướng dẫn của TS. Ngô Văn Định, Trường Đại học Khoa Học - Đại học Thái Nguyên. Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới TS. Ngô Văn Định, người đã định hướng chọn đề tài và tận tình hướng dẫn để tôi hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn chân thành tới Phòng Đào tạo, các thầy cô giáo dạy cao học chuyên ngành Phương pháp toán sơ cấp, trường Đại học Khoa Học - Đại học Thái Nguyên đã giúp đỡ tôi trong suốt quá trình học tập và hoàn thành luận văn tốt nghiệp. Tôi xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, người thân đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn. Thái Nguyên, tháng 6 năm 2017 Tác giả Nguyễn Văn Quyên ii Mở đầu Dãy số Fibonacci {Fn } là dãy số được rất nhiều người biết đến, quan tâm và nghiên cứu. Có rất nhiều tính chất thú vị của dãy số này đã được tìm ra. Dãy số Fibonacci được định nghĩa bởi phương trình sai phân tuyến tính cấp hai thuần nhất Fn+2 = Fn+1 + Fn , n ≥ 0, với điều kiện ban đầu F0 = F1 = 1. Khái niệm về dãy Fibonacci được mở rộng theo nhiều cách khác nhau. Mục đích của luận văn này là trình bày lại một số kết quả về một số dãy Fibonacci {xn } suy rộng xác định bởi xn+2 = pxn+1 + qxn , n ≥ 0, với x0 = a, x1 = b, trong đó p, q, a, b là các số nguyên không âm. Đầu tiên, Luận văn trình bày lại kết quả của Panwar, Singh và Gupta [9] về một số tính chất thú vị của hai dãy Fibonacci suy rộng {Vn } và {Un } được xác định bởi Vn+2 = Vn+1 + 2Vn , n ≥ 0, với V0 = 2, V1 = 2, và Un+2 = Un+1 + 2Un , n ≥ 0, với U0 = 2, U1 = 0. 1 Tiếp theo, Luận văn trình bày một số kết quả của Hoggatt và Long [4] về dãy Fibonacci suy rộng {un } được xác định bởi phương trình sai phân un+2 = pun+1 + qun , n ≥ 0, với u0 = 0, u1 = 1, trong đó p, q là hai số nguyên dương. Cuối cùng, Luận văn trình bày lại các kết quả của Aoki và Sakai [2, 3] về dãy Fibonacci suy rộng {Gn } xác định bởi Gn+2 = Gn+1 + Gn , n ≥ 1, với G1 = a, G2 = b, trong đó a, b là hai số nguyên. Cấu trúc của luận văn Luận văn được trình bày thành 2 chương: • Chương 1: Dãy Fibonacci suy rộng. Trong chương này, chúng tôi trình bày sơ lược về lý thuyết về phương trình sai phân tuyến tính cấp hai thuần nhất; khái niệm về dãy Fibonacci suy rộng và các kết quả của Panwar, Singh và Gupta [9]. • Chương 2: Tính chia hết của các số Fibonacci suy rộng. Chương này trình bày về một số kết quả của Hoggatt và Long [4]; các kết quả của Aoki và Sakai [2, 3]. 2 Chương 1 Dãy Fibonacci suy rộng Trong chương mở đầu này, chúng tôi trình bày sơ lược về phương trình sai phân tuyến tính cấp hai thuần nhất đặc biệt là về nghiệm của phương trình trong trường hợp phương trình đặc trưng có hai nghiệm phân biệt. Sau đó, chúng tôi trình bày khái niệm về dãy Fibonacci suy rộng và các kết quả của Panwar, Singh và Gupta [9] về hai trường hợp riêng của dãy Fibonacci suy rộng. 1.1 Phương trình sai phân tuyến tính cấp 2 Trong mục này, chúng tôi nhắc lại khái niệm về phương trình sai phân tuyến tính cấp hai thuần nhất và đặc biệt chúng tôi trình bày về công thức nghiệm của phương trình này trong trường hợp đa thức đặc trưng có hai nghiệm phân biệt. Đây là những kiến thức cần thiết cho các nội dung của các phần sau trong Luận văn. Nội dung về phương trình sai phân chúng tôi tham khảo trong tài liệu [7]. Định nghĩa 1.1. Phương trình có dạng un+2 = Aun+1 + Bun , n = 1, 2, ..., (1.1) 3 trong đó A, B là các hằng số, được gọi là phương trình sai phân tuyến tính cấp hai thuần nhất. Để tìm nghiệm của phương trình sai phân (1.1), chúng ta xét phương trình bậc hai α2 − Aα − B = 0. (1.2) Phương trình bậc hai này được gọi là phương trình đặc trưng của phương trình sai phân (1.1). Định lý sau đây cho chúng ta công thức nghiệm của phương trình sai phân (1.1) trong trường hợp phương trình đặc trưng (1.2) có hai nghiệm phân biệt. Ở đây, chúng tôi chỉ trình bày nội dung của định lý để có thể sử dụng trong các phần sau mà không trình bày chứng minh. Định lý 1.2 ([7, Theorem 10.1]). Giả sử phương trình đặc trưng (1.2) có hai nghiệm phân biệt α1 và α2 . Khi đó phương trình sai phân (1.1) có nghiệm là n n un = C1 α1 + C2 α2 , n = 1, 2, ..., (1.3) trong đó C1 và C2 là những số bất kì. Chúng ta cũng cần chú ý rằng, nếu biết điều kiện ban đầu u0 và u1 thì các hằng số C1 và C2 hoàn toàn được xác định. Khi đó, dãy số {un }∞ được xác định bởi n=1 n−1 n−1 aα1 − bα2 un = , n ≥ 2, α1 − α2 (1.4) trong đó α1 , α2 là hai nghiệm của phương trình đặc trưng (1.2) và a = u2 − u1 α2 , b = u2 − u1 α1 . Công thức (1.4) được gọi là công thức 4 Binet của dãy {un }. Tên công thức này được đặt theo tên của nhà toán học người Pháp Jacques Philippe Marie Binet do ông đã tìm ra công thức Binet cho dãy Fibonacci vào thế kỷ 19. Ví dụ 1.3. Ta sẽ xét ở đây một ví dụ rất quen thuộc về dãy số Fibonacci {Fn } được xác định bởi phương trình sai phân Fn+2 = Fn+1 + Fn , (1.5) với điều kiện ban đầu F1 = 1, F2 = 1. Phương trình đặc trưng của phương trình (1.5) là λ2 − λ − 1 = 0. Phương trình đặc trưng này có hai nghiệm phân biệt là √ √ 1− 5 1+ 5 và λ2 = . λ1 = 2 2 Do đó, nghiệm tổng quát của phương trình (1.5) là √ n √ n 1+ 5 1− 5 F n = C1 + C2 , n = 1, ... 2 2 Từ điều kiện ban đầu F1 = 1, F2 = 1 ta có hệ phương trình  √ √  1− 5 1+ 5 C  1 + C2 = 1,   2 2 √ 2 √ 2   C1 1 + 5 + C2 1 − 5  = 1.  2 2 1 Giải hệ phương trình này ta được C1 = −C2 = √ . Từ đó suy ra số 5 hạng tổng quát của dãy số Fibonacci là √ n √ n 1+ 5 1 1− 5 Fn = √ − , n = 1, 2, ... 2 2 5 5 Ví dụ 1.4. Ta tiếp tục xét một ví dụ khác cũng là một dãy số quen thuộc - dãy số Lucas {Ln }. Dãy Lucas cũng được xác định bởi phương trình sai phân (1.5) nhưng với điều kiện ban đầu L0 = 2 và L1 = 1. Vì vậy, số hạng tổng quát của dãy Lucas cũng có dạng: Ln = C1 λn + C2 λn , với n = 1, 2, ..., 2 1 trong đó √ √ 1+ 5 1− 5 λ1 = và λ2 = . 2 2 Với điều kiện ban đầu L0 = 2, L1 = 1, ta được:   C1 + C2 = 2,  C λ + C λ = 1. 1 1 2 2 Giải hệ này ta được C1 = 1, C2 = 1. Vậy ta có √ n √ 1+ 5 1− 5 + Ln = λn + λn = 1 2 2 2 1.2 n . Định nghĩa dãy Fibonacci suy rộng Khái niệm của dãy Fibonacci được mở rộng dưới nhiều dạng khác nhau. Chẳng hạn như, Kalman và Mena [6] đã nghiên cứu dãy số xác định bởi Fn = aFn−1 + bFn−2 , n ≥ 2, với F0 = 0 và F1 = 1. Ngoài ra, Horadam [5] cũng đã định nghĩa một dãy Fibonacci suy rộng {Hn } bởi Hn = Hn−1 + Hn−2 , n ≥ 3, với H1 = p và H2 = p + q, 6 trong đó p và q là hai số nguyên bất kỳ. Ở đây, ta sẽ định nghĩa dãy Fibonacci suy rộng như sau: Định nghĩa 1.5. Dãy Fibonacci suy rộng {Fn } được định nghĩa bởi phương trình sai phân Fk = pFk−1 + qFk−2 , k ≥ 2, (1.6) với điều kiện ban đầu F1 = a, F2 = b, trong đó p, q, a, b là các số nguyên dương. Với các giá trị khác nhau của p, q, a, b, dãy số xác định bởi Định nghĩa 1.5 cho ta rất nhiều dãy số khác nhau, trong đó có những dãy số mà ta đã biết đến: Với p = q = a = b = 1, ta thu được dãy Fibonacci thông thường; Với a = 2, p = q = b = 1, ta thu được dãy Lucas; ... 1.3 Một số tính chất của dãy Fibonacci suy rộng Trong mục này, chúng tôi sẽ trình bày các kết quả nghiên cứu của Panwar, Singh và Gupta [9] về hai trường hợp riêng của dãy Fibonacci suy rộng xác định bởi (1.6): • Dãy {Vk }k≥0 xác định bởi (1.6) với p = 1, q = a = b = 2, tức là: Vk = Vk−1 + 2Vk−2 , k ≥ 2, với V0 = 2, V1 = 2; • Dãy {Uk }k≥0 xác định bởi (1.6) với p = 1, q = a = 2, b = 0, tức là: Uk = Uk−1 + 2Uk−2 , k ≥ 2, với U0 = 2, U1 = 0. 7 Trước tiên, tương tự như các dãy số xác định bởi phương trình sai phân, hai dãy số này cũng có công thức Binet xác định số hạng tổng quát của chúng. Gọi R1 = 2 và R2 = −1 là hai nghiệm của phương trình đặc trưng x2 − x − 2 = 0. Khi đó, công thức Binet của hai dãy Fibonacci suy rộng {Un } và {Vn } được xác định bởi mệnh đề dưới đây. Mệnh đề 1.6 (Công thức Binet). Số hạng Fibonacci thứ k của dãy Fibonacci suy rộng Uk , Vk được xác định bởi k+1 k+1 R1 − R2 ; (i) Vk = 2 R1 − R2 k−1 k−1 R1 − R2 . (ii) Uk = 4 R1 − R2 Chứng minh. Chúng ta có thể sử dụng Định lý 1.2 để chứng minh công thức Binet hoặc chúng ta có thể chứng minh trực tiếp bằng phương pháp quy nạp. Ở đây, chúng tôi sẽ trình bày chứng minh theo quy nạp cho công thức Binet của dãy {Vn }. Chứng minh công thức Binet cho dãy {Un } hoàn toàn tương tự. Ta dễ kiểm tra được rằng, với n = 0, n = 1 định lý đúng. Giả sử định lý đúng với mọi r thỏa mãn 0 ≤ r ≤ s + 1, tức là r+1 r+1 R1 − R2 Vr = 2 , với mọi r thỏa mãn 0 ≤ r ≤ s. R1 − R2 8 Khi đó từ định nghĩa dãy Fibonacci suy rộng {Vn } ta có (lưu ý rằng R1 và R2 là hai nghiệm của phương trình x2 − x − 2 = 0) Vs+1 = Vs + 2Vs−1 r+2 r+2 R1 − R2 =2 . R1 − R2 Như vậy công thức đúng với r = s + 1. Theo nguyên lý quy nạp toán học, công thức đúng với mọi r ≥ 0. Năm 1879, nhà thiên văn học người Pháp Jean-Diminique Cassini đã tìm ra một đẳng thức cho dãy số Fibonacci 2 Fn−1 Fn+1 − Fn = (−1)n . Sau đó, công thức này đã được nhà toán học người Bỉ Eugene Charles Catalan tổng quát hóa thành 2 Fn − Fn−r Fn+r = (−1)n−r Fr2 . Định lý sau đây cho ta các đẳng thức tương tự đối với hai dãy số Fibonacci suy rộng {Un } và {Vn }. Định lý 1.7 (Đẳng thức Catalan). Với hai số tự nhiên r, n thỏa mãn r + 1 ≤ n ta có 2 2 (i) Vn−r−1 Vn+r−1 − Vn−1 = (−1)n−r+1 2n−r Vr−1 ; 2 2 (ii) Un−r+1 Un+r+1 − Un+1 = (−1)n−r+1 2n−r Ur+1 . Chứng minh. Ta sẽ chứng minh đẳng thức (i), đẳng thức (ii) được 9 chứng minh tương tự. Sử dụng công thức Binet của dãy {Vn }, ta có n−r n+r n−r n+r n n R1 − R2 R1 − R2 R1 − R2 =2 2 −4 Vn−r−1 Vn+r−1 − R1 − R2 R1 − R2 R1 − R2 r r 4 R2 R1 n n n = −(R1 R2 ) − (R1 R2 ) + 2(R1 R2 ) 9 R1 R2 r r n −4(−2) R2 R1 = + −2 9 R1 R2 n+1−r n+2 r 2 r R1 − R2 (−1) 2 = r R1 − R2 (−2) r 2 r R1 − R2 n+1−r n−r 2 . = (−1) 2 R1 − R2 2 2 Vn−1 2 2 Vậy Vn−r−1 Vn+r−1 − Vn−1 = (−1)n−r+1 2n−r Vr−1 . Trong đẳng thức Catalan, cho r = 1, ta thu được: Định lý 1.8 (Đẳng thức Cassini). Với số tự nhiên n ≥ 2, ta có 2 (i) Vn−2 Vn − Vn−1 = (−1)n 2n+1 ; 2 (ii) Un+2 Un − Un+1 = (−1)n 2n+3 . Dãy số Fibonacci thỏa mãn đẳng thức sau đây, gọi là Đẳng thức d’Ocagne: Fm Fn+1 − Fm+1 Fn = (−1)n Fm−n . Định lý sau đây cho ta các đẳng thức tương tự đối với hai dãy Fibonacci suy rộng {Un } và {Vn }. Định lý 1.9 (Đẳng thức d’Ocagne). Với hai số nguyên dương n và m bất kỳ, ta có (i) Um+1 Un − Um Un+1  8 n m  (R1 + R1 ), n chẵn, m lẻ, 3 =  − 8 (Rn + Rm ), n lẻ, m chẵn;  1 3 1 10   4 n m  − (R1 + R1 ), n chẵn, m lẻ, 3 (ii) Vm Vn−1 − Vm−1 Vn = 4 n  (R + Rm ), n lẻ, m chẵn.  1 3 1 Chứng minh. Ta sẽ chứng minh đẳng thức (i), đẳng thức (ii) được chứng minh hoàn toàn tương tự. Ta có 16 n−1 n−1 m−1 m−1 n n m m Um+1 Un − Um Un+1 = (R1 − R2 )(R1 − R2 ) − (R1 − R2 )(R1 − R2 ) 9 16 m−1 n m−1 n m n−1 m n−1 = R1 R2 − R1 R2 + R2 R1 − R2 R1 9 16 1 n m m n = − 1 (R1 R2 − R1 R2 ) 9 R1 R2 8 m n n m = (R1 R2 − R1 R2 ). 3 Từ đây suy ra   8 n m  (R1 + R1 ), n chẵn, m lẻ, 3 Um+1 Un − Um Un+1 =  − 8 (Rn + Rm ), n lẻ, m chẵn.  1 3 1 Định lý sau đây cho ta thấy rằng giới hạn của thương của hai số hạng liên tiếp của hai hãy Fibonacci suy rộng bằng nghiệm dương của phương trình đặc trưng tương ứng với phương trình sai phân xác định hai dãy này. Định lý 1.10. Ta có 1. lim Vk−1 Vk−2 = R1 ; 2. lim Uk+1 Uk = R1 . k→∞ k→∞ Chứng minh. 1. Sử dụng công thức Binet ta có lim k→∞ Vk−1 Vk−2 = k R1 lim k→∞ Rk−1 1 − − k R2 k−1 R2 1− = lim k→∞ 1 R1 − R2 R1 R2 R1 k k 1 R2 11 Ta có lim k R2 R1 k→∞ = 0 vì |R2 | < R1 . Từ đó, ta thu được điều phải chứng minh. Chứng minh 2. Tương tự như chứng minh 1. Định lý sau đây cho ta đẳng thức khác của hai dãy Fibonacci suy rộng {Un } và {Vn }. Định lý 1.11. Với dãy Fibonacci suy rộng {Vn } ta có 34(16)k + 10(4)k + 1 2 2 1. V2k + V2k+2 = 8 9 2 2 2. V2k − V2k+2 = −16 9 12(16)k + (4)k Chứng minh. 1. Sử dụng công thức Binet, ta có 2 2 V2k +V2k+2 = = = = = = 4 9 4 9 4 9 4 9 8 9 4 4k+2 2k+1 2k+3 4k+2 4k+6 4k+6 R1 + R2 − 2(R1 R2 ) + R1 + R2 − 2(R1 R2 ) 9 4k+2 4k 4k+2 4k R1 1 + R1 + R2 1 + R2 − 2(R1 R2 ) 4k+2 4k+2 17R1 + 2R2 − 10(R1 R2 ) 4k 4k 68R1 + 2R2 + 20(R1 R2 ) k k 1 + (R1 R2 ) 2 2k+1 2k k k 2k+1 68(16) + 2 + 20(4) 34(16) + 1 + 10(4) . Chứng minh 2. Tương tự như chứng minh 1. Hoàn toàn tương tự, ta có các đẳng thức sau đối với dãy Fibonacci suy rộng {Un }. 12 Định lý 1.12. Với dãy {Uk }k≥0 ta có 2 2 1. U2k + U2k+2 = 16 9 2 2 2. U2k − U2k+2 = −48 9 17 (16)k 4 + 5(4)k ; 5(4)2k−1 + (4)k . 13 Chương 2 Tính chia hết của các số Fibonacci suy rộng Trong chương này, chúng tôi tập trung trình bày lại một số kết quả về tính chia hết của một số dãy Fibonacci suy rộng. Cụ thể, chúng tôi trình bày lại một số kết quả của Hoggatt và Long [4]; các kết quả của Aoki và Sakai [2, 3]. 2.1 Kết quả của Hoggatt và Long Trong mục này, chúng tôi trình bày các kết quả của Hoggatt và Long [4] về một số tính chất liên quan đến tính chia hết của dãy Fibonacci suy rộng {un } xác định bởi un+2 = pun+1 + qun , với u0 = 0 và u1 = 1, trong đó, p và q là hai số nguyên dương. Trước tiên, ta thấy rằng phương trình đặc trưng tương ứng x2 − px − q = 0 có hai nghiệm α= p+ p2 + 4q p− và β = 2 p2 + 4q . 2 14 Do đó, công thức Binet cho dãy {un } là αn − β n un = , n ≥ 0. α−β Sử dụng công thức Binet này, ta chứng minh được đẳng thức sau đây: Định lý 2.1. Với m ≥ 0 và n ≥ 0, ta có um+n+1 = um+1 un+1 + qum un . Ta sẽ chứng minh rằng, với mọi n ≥ 0, un và un+1 là nguyên tố cùng nhau. Trước tiên, ta cần bổ đề sau đây: Bổ đề 2.2. Với mọi n > 0, ta có (q, un ) = 1. Chứng minh. Ta thấy điều khẳng định đúng với n = 1 khi đó u1 = 1. Giả sử rằng bổ đề đúng với k bất kì, k ≥ 1. Khi đó ta có uk+1 = puk + quk−1 . Khẳng định này đúng với n = k + 1, và vì thế khẳng định đúng với mọi n ≥ 1. Định lý 2.3. Với n ≥ 0, ta có (un , un+1 ) = 1. Chứng minh. Định lý đúng với n = 0 và n = 1. Khi đó u0 = 0, u1 = 1, và u2 = p. Giả sử rằng định lý đúng với n = k − 1, trong đó k là số nguyên cố định, k ≥ 2 và cho d(p, q) = (uk , uk+1 ). Khi đó uk+1 = puk + quk−1 . 15 Điều này có nghĩa rằng d(p, q)|uk−1 q. Nhưng theo Bổ đề 2.2 ta có (d(p, q), q) = 1, và do đó d(p, q)|uk−1 . Nhưng khi d(p, q)|1 thì (uk−1 , uk ) = 1, và khi đó định lý đúng với mọi n ≥ 0. Điều phải chứng minh. Bổ đề 2.4. Với n ≥ 0, ta có [(n−1)/2] un = i=0 n − i − 1 n−2i−1 i p q. i Chứng minh. Ta quy ước tổng rỗng bằng không nên kết quả đúng với n= 0. Với n = 1, tổng chỉ chứa một số hạng   0   p 0 q 0 = 1 = u1 . 0 Giả sử đẳng thức đúng với n = k −1 và n = k, với k cố định và k ≥ 1. Khi đó uk+1 = k + quk−1  pu   [(k−1)/2] [(k−2)/2] k−i−1 k−i−2  pk−2i q i +  pk−2i−2 q i+1 = i=0 i=0 i i     [(k−1)/2] [k/2] k−i−1 k−i−2  pk−2i q i +  pk−2i q i = i=0 i=0 i i−1   [k/2] k−i  pk−2i q i . = i=0 i Do đó kết quả đúng với n = k + 1, và do đó cũng đúng với mọi n ≥ 0. Điều phải chứng minh. 16