Tài liệu Về giá trị lớn nhất của dãy stern

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM THỊ THU THỦY VỀ GIÁ TRỊ LỚN NHẤT CỦA DÃY STERN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN, 10/2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM THỊ THU THỦY VỀ GIÁ TRỊ LỚN NHẤT CỦA DÃY STERN Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC GIÁO VIÊN HƯỚNG DẪN PGS. TS. NÔNG QUỐC CHINH THÁI NGUYÊN, 10/2018 iii Mục lục Bảng ký hiệu 1 Mở đầu 2 Chương 1. Một số kiến thức chuẩn bị 1.1 Dãy số Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Mảng diatomic của Stern . . . . . . . . . . . . . . . . . . . . 1.3 Dãy diatomic của Stern . . . . . . . . . . . . . . . . . . . . . 4 4 8 9 Chương 2. Về giá trị lớn nhất của dãy Stern 14 2.1 Giá trị lớn nhất trên một hàng của mảng diatomic của Stern 14 2.2 Giá trị lớn thứ hai trên mỗi hàng của mảng diatomic của Stern 16 2.3 Giá trị lớn thứ ba trên mỗi hàng của mảng diatomic của Stern 22 2.4 Dãy w(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Kết luận 37 Tài liệu tham khảo 38 1 Bảng ký hiệu N Z≥0 Q+ (Fn )n∈N Fn (S(n))n∈N S(n) (w(n))n∈N SEA nr , n∗r Lk (r) gk (n) tập hợp các số tự nhiên tập hợp các số nguyên không âm tập hợp các số hữu tỉ dương dãy số Fibonacci số Fibonacci thứ n dãy Stern số Stern thứ n dãy sinh bởi dãy Stern thuật toán Euclide chậm số thứ tự mà phần tử S(nr ) và S(n∗r ) là phần tử lớn nhất trên hàng thứ r phần tử lớn nhất trên hàng thứ r ước chung lớn nhất của n + k + 1 số liền nhau trong dãy (w(n))n∈N 2 Mở đầu Tam giác Pascal là khái niệm toán học rất quen thuộc đối với mỗi người học toán. Trong tam giác số này, bắt đầu từ hàng thứ hai, mỗi số ở hàng thứ n, từ cột thứ hai đến cột thứ n−1 bằng tổng hai số đứng ở hàng trên cùng cột và cột trước nó. Năm 1858, Stern đã nghiên cứu mảng diatomic, một mảng có nhiều tính chất tương tự tam giác Pascal. Mảng diatomic và dãy diatomic của Stern đã được nhiều nhà toán học nghiên cứu, tuy nhiên cho đến nay vẫn có nhiều kết quả mới của nó được công bố. Một trong các kết quả nghiên cứu gần đây nhất về dãy Stern là về giá trị lớn nhất, giá trị lớn thứ hai, giá trị lớn thứ ba của các hàng trong mảng diatomic của dãy Stern. Với mong muốn tìm hiểu sâu hơn về vấn đề này, tôi chọn đề tài “Về giá trị lớn nhất của dãy Stern” làm đề tài luận văn cao học của mình. Mục tiêu của luận văn là đọc hiểu và trình bày lại hai bài báo [4] và [9]. Ngoài phần mở đầu và kết luận, nội dung chính của luận văn được trình bày trong hai chương: Chương 1. Một số kiến thức chuẩn bị. Chương này trình bày về dãy số Fibonacci, dãy số Stern và một số tính chất của dãy Stern. Chương 2. Giá trị lớn nhất của dãy Stern. Trong chương trình bày về các giá trị lớn nhất như giá trị lớn nhất, giá trị lớn thứ hai, giá trị lớn thứ ba của dãy S(n). Ngoài ra, chương này còn trình bày thêm về dãy w(n) và giá trị lớn nhất của dãy w(n). Để hoàn thành bản luận văn này, tôi xin được bày tỏ lòng biết ơn sâu sắc tới PGS. TS Nông Quốc Chinh, người thầy nhiệt huyết đã truyền thụ kiến thức, đã chỉ ra hướng đề tài và tận tình hướng dẫn trong suốt quá trình làm luận văn. Đồng thời, tôi xin chân thành cảm ơn các thầy, cô phản biện đã dành thời gian đọc và đóng góp những ý kiến quý báu cho bản luận văn này. Tôi xin chân thành cảm ơn toàn thể các thầy cô trong Khoa Toán – Tin, Trường Đại học Khoa học – Đại học Thái Nguyên đã tận tình hướng dẫn, truyền đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn. Qua luận văn này, tôi cũng muốn gửi lời cảm ơn tới gia đình, bạn 3 bè đã luôn động viên, giúp đỡ tôi trong thời gian làm luận văn. Mặc dù đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và năng lực của mình. Tuy nhiên, luận văn không thể tránh khỏi những thiếu sót, tôi rất mong nhận được những đóng góp quý báu của thầy cô và các bạn. Thái Nguyên, ngày 22 tháng 9 năm 2018 Tác giả luận văn Phạm Thị Thu Thủy 4 Chương 1 Một số kiến thức chuẩn bị 1.1 Dãy số Fibonacci Định nghĩa 1.1.1. Dãy số Fibonacci, ký hiệu bởi {Fn }, được định nghĩa bởi hệ thức truy hồi sau: Fn = Fn−1 + Fn−2 , n ≥ 2, với F0 = 0, F1 = 1. Theo định nghĩa, ta có dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Số hạng tổng quát của dãy số Fibonacci được xác định bởi công thức Binet dưới đây: √ √ 1+ 5 1− 5 Mệnh đề 1.1.2 (Công thức Binet). Với n ∈ Z, α = và β = , 2 2 ta có αn − β n Fn = . α−β Tiếp theo chúng tôi trình bày một số tính chất của dãy số Fibonacci, các kết quả này được sử dụng trong các chứng minh ở phần sau. Mệnh đề 1.1.3 ([11, Bổ đề 2.1]). Với số nguyên n ≥ 1, ta có Fn2 − Fn−1 Fn+1 = (−1)n−1 . Chứng minh. Ta sẽ chứng minh bằng quy nạp theo n. Với n = 1, ta có F12 − F0 F2 = 12 − 0.1 = 1 = (−1)0 . (1.1) 5 Giả sử, đẳng thức đúng với n > 1, ta chứng minh đẳng thức đúng với n + 1. Thật vậy, ta có 2 Fn+1 − Fn Fn+2 = (Fn + Fn−1 )2 − Fn (Fn + Fn+1 ) 2 = Fn2 + 2Fn Fn−1 + Fn−1 − Fn2 − Fn Fn+1 2 = 2Fn Fn−1 + Fn−1 − Fn Fn+1 2 = 2Fn Fn−1 + Fn−1 − Fn (Fn + Fn−1 ) 2 = Fn−1 + Fn Fn−1 − Fn2 = Fn−1 (Fn−1 + Fn ) − Fn2 = Fn−1 Fn+1 − Fn2 = −(−1)n−1 = (−1)n . Suy ra điều phải chứng minh. Mệnh đề 1.1.4 ([11, Bổ đề 2.1]). Với hai số nguyên dương m, n bất kỳ, ta có đẳng thức sau Fn+m = Fn−1 Fm + Fn Fm+1 . (1.2) Chứng minh. Ta chứng minh bằng quy nạp theo m. Với m = 1, ta có Fn+1 = Fn−1 F1 + Fn F2 = Fn−1 + Fn . Với m = 2, ta có Fn+2 = Fn−1 F2 + Fn F3 = Fn−1 + 2Fn = Fn+1 + Fn . Giả sử, đẳng thức đúng với m > 2, ta chứng minh đẳng thức đúng với m + 1. Thật vậy, ta có Fn+m+1 = Fn+m−1 + Fn+m = Fn−1 Fm−1 + Fn Fm + Fn−1 Fm + Fn Fm+1 = Fn−1 (Fm−1 + Fm ) + Fn (Fm + Fm+1 ) = Fn−1 Fm+1 + Fn Fm+2 . Suy ra điều phải chứng minh. Hệ quả 1.1.5 ([11, Hệ quả 2.2]). 1. Với số nguyên n ≥ 1, ta có F2n = Fn (Fn−1 + Fn+1 ) . (1.3) 6 2. Với mọi số nguyên không âm n, ta có 2 F2n+1 = Fn2 + Fn+1 . (1.4) 3. Với mọi n ≥ 1, chúng ta có F2n+1 = Fn−1 Fn+1 + Fn Fn+2 . (1.5) 4. Với mọi n ≥ 1, chúng ta có F2n+1 = Fn+1 Fn+2 − Fn−1 Fn . (1.6) Hệ quả 1.1.6 (Tính chất d’Ocagne). Với hai số nguyên m, n và m ≥ n, ta có Fm Fn+1 − Fm+1 Fn = (−1)n Fm−n . (1.7) Mệnh đề 1.1.7 ([11, Bổ đề 3.1]). Với số nguyên n ≥ 1, ta có Fn Fn+1 − Fn−1 Fn+2 = (−1)n−1 . (1.8) Một cách tổng quát ta có mệnh đề dưới đây: Mệnh đề 1.1.8 ([12, Bổ đề 5]). Giả sử a, b, c, d là bốn số nguyên dương với a + b = c + d và b ≥ max {c, d}. Khi đó, ta có Fa Fb − Fc Fd = (−1)a+1 Fb−c Fb−d . (1.9) Mệnh đề 1.1.9 ([11, Bổ đề 2.4]). 1. Nếu n ≥ 6 thì ta có Fn−2 Fn−1 > Fn+1 . (1.10) 2. Với mỗi n ≥ 3, chúng ta có F3n−1 (Fn + Fn−3 ) > Fn−2 Fn−1 Fn Fn+1 . (1.11) Mệnh đề 1.1.10 ([12, Bổ đề 15]). 1. Với n ≥ 1, chúng ta có F6n+2 > F2n (F2n−2 + F2n )(F2n+2 + F2n+4 ). (1.12) 2. Với số nguyên dương n, ta có 2F4n (F4n + F4n+2 ) > F2n+2 F4n+3 (F2n−2 + F2n ). (1.13) 7 3. Với n ≥ 2, chúng ta có F4n−2 (F2n−2 + F2n )(F2n+2 + F2n+4 ) > F4n (F4n−2 + F4n ). (1.14) Mệnh đề 1.1.11 ([12, Bổ đề 40]). Với mọi n ≥ 1, chúng ta có 2F3n+3 > Fn Fn+1 Fn+6 . (1.15) Chứng minh. Ứng dụng đẳng thức (1.2) nhiều lần, ta thu được F3n+3 = Fn F2n+2 + Fn+1 F2n+3 > Fn Fn+3 = Fn (Fn Fn+1 + Fn+1 Fn+2 ) + Fn+1 (Fn Fn+2 + Fn+1 Fn+3 ) 2 = Fn Fn+1 (Fn + 2Fn+2 ) + Fn+1 (Fn + 2Fn+1 ) 2 = Fn Fn+1 (Fn + Fn+1 + 2Fn+2 ) + 2Fn+1 > Fn Fn+1 (3Fn+2 + 2Fn+1 ) = Fn Fn+1 Fn+5 . Vì thế ta có 2F3n+3 − Fn Fn+1 Fn+6 > 2Fn Fn+1 Fn+5 − Fn Fn+1 Fn+6 = Fn Fn+1 (2Fn+5 − Fn+6 ) > 0. Hoàn thành việc chứng minh. Mệnh đề 1.1.12 ([12, Bổ đề 42]). Với mọi n ≥ 2, chúng ta có F2n F2n+1 − Fn+1 Fn+4 F2n−2 < 0. Chứng minh. Áp dụng các hệ thức (1.6) và (1.9) ta có Fn+2 Fn+3 − Fn Fn+1 = F2n+3 , Fn+1 Fn+4 − Fn+2 Fn+3 = (−1)n . Suy ra Fn+1 Fn+4 = Fn Fn+1 + F2n+3 + (−1)n > F2n+3 + 2. Vì thế, ta có F2n F2n+1 − Fn+1 Fn+4 F2n−2 < F2n F2n+1 − (F2n+3 + 2)F2n−2 = (F2n F2n+1 − F2n−2 F2n+3 ) − 2F2n−2 = 2 − 2F2n−2 ≤ 0. Suy ra điều cần chứng minh. (1.16) 8 1.2 Mảng diatomic của Stern Năm 1858 trong một bài báo công bố nghiên cứu của mình, M.A. Stern đã nghiên cứu tính chất của một dãy được xây dựng tương tự tam giác Pascal, đó là mảng tam giác được gọi là mảng diatomic, bằng cách chọn hai giá trị a, b ở hàng đầu, hàng thứ hai có ba phần tử xây dựng bằng cách viết lại hàng một, và chèn tổng của hai phần tử ở hàng một,... tương tự như vậy: hàng thứ n được xây dựng bằng cách viết lại hàng n − 1 và chèn vào giữa hai phần tử bất kỳ của hàng n − 1 giá trị tổng của 2 phần tử đó,. . . a a b a a+b b 2a + b a+b a + 2b b a 3a + b 2a + b 3a + 2b a + b 2a + 3b a + 2b a + 3b b .. . Bảng 1.1: Mảng diatomic tổng quát Tính chất của mảng ditomic tổng quát. (Xem Bảng 1.1). Kí hiệu r là chỉ số của hàng thứ r trong mảng diatomic (Bảng 1.1); với quy ước hàng đầu tiên ứng với hai phần tử ban đầu cho r trước là a và b có chỉ số r = 0. Khi đó, ta có một số tính chất sau: a) Các số a và b luôn đứng ở vị trí đầu và cuối mỗi hàng. b) Số (a + b) luôn là phần tử nằm ở chính giữa mỗi hàng. c) Nếu một hàng có k phần tử, thì hàng tiếp theo sẽ có 2k − 1 phần tử. d) Số các phần tử nằm trên hàng thứ r là 2r + 1, và tất cả các phần tử của hàng này sẽ có mặt trên mọi hàng dưới nó (trên hàng thứ r + k , mọi k ≥ 1). e) Nếu ta kí hiệu Sr (a, b) là tổng tất cả các phần tử nằm trên hàng r, khi đó ta có: 3r + 1 (a + b) Sr (a, b) = 2 f) Ta luôn có: Sr (a, b) = Sr (b, a). g) Ta luôn có: Sr (a + a0 , b + b0 ) = Sr (a, b) + Sr (a0 , b0 ). 9 h) Nếu (a, b) = 1 (a và b là hai số nguyên tố cùng nhau) thì hai phần tử bất kì liền kề nhau trên một hàng luôn nguyên tố cùng nhau; Hơn nữa bộ ba bất kì liền nhau trên một hàng: m, n, s (với n = m + s), ta luôn có: (m, s) = 1. 1.3 Dãy diatomic của Stern Stern đã nghiên cứu tính chất của mảng diatomic tổng quát, ông đã kiểm tra trường hợp đặc biệt với a = b = 1. Khi đó, mảng diatomic được cho như trong Bảng 1.2. 1 1 1 2 1 1 3 2 3 1 1 5 4 7 1 4 3 5 2 5 3 4 1 3 8 5 7 2 7 5 8 3 7 4 5 1 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1 Bảng 1.2: Mảng diatomic Trong Bảng 1.2 nếu ta đánh số thứ tự như Bảng 1.3, ta nhận được một dãy số nguyên dương (S(n)) với n ∈ N. Với quy ước S(0) = 0, ta thấy dãy số trên có tính chất đặc biệt sau: ( S(2n) = S(n) (1.17) S(2n + 1) = S(n) + S(n + 1), n ≥ 1. S(1) S(4) S(8) S(9) S(2) S(2) S(3) S(4) S(5) S(6) S(7) S(8) S(10) S(11) S(12) S(13) S(14) S(15) S(16) S(16) S(17) S(18) S(19) S(20) S(21) S(22) S(23) S(24) S(25) S(26) S(27) S(28) S(29) S(30) S(31) S(32) Bảng 1.3: Mảng diatomic Định nghĩa 1.3.1. Dãy số nguyên dương được xác định theo công thức truy hồi : ( S(2n) = S(n) (1.18) S(2n + 1) = S(n) + S(n + 1), n ≥ 1, với S(0) = 0, S(1) = 1 được gọi là dãy Stern. 10 Một trong các tính chất hiển nhiên nhất của mảng diatomic trong Bảng 1.2 là tính đối xứng. Trong mỗi hàng của mảng diatomic, tính đối xứng được ký hiệu là S(n) = S(n∗ ) trong đó n∗ := 3 · 2r − n với 2r ≤ n ≤ 2r+1 . (1.19) Hàng thứ r của mảng diatomic (Bảng 1.2) xác định các số Stern gồm các phần tử S(n) với 2r ≤ n ≤ 2r+1 . Nhận xét 1.3.2. Dãy Stern là một dãy các số nguyên dương được lấy trong mảng diatomic của Stern khi a = b = 1 (Trong Bảng 1.2). Các hàng trong Bảng 1.2 là đối xứng qua phần tử đứng giữa là số 2. Nên ngoài các tính chất đã cho trong mảng diatomic tổng quát (Bảng 1.1) ta còn nhận thấy một số các tính chất sau trong Bảng 1.2: Tính chất 1.3.3. (a) Các hàng trong mảng diatomic là đối xứng qua phần tử đứng giữa là số 2. (b) Tổng các phần tử trên hàng thứ r của Bảng 1.2 bằng 3r + 1. Mệnh đề 1.3.4. Số tất cả các phần tử từ hàng đầu tiên (r = 0) đến hết hàng r+1 thứ r trong mảng diatomic là 2r+1 + r và tổng của chúng là 3 2 +1 + r. Chứng minh. Ta chứng minh mệnh đề này bằng quy nạp. - Với k = 1, khi đó hàng 0 và hàng 1 có 5 = 21+1 + 1 phần tử và tổng các 1+1 phần tử đó là 6 = 3 2 +1 + 1. Như vậy, mệnh đề đúng với k = 1. - Giả sử mệnh đề đúng với mọi k < r. - Khi đó số các phần tử từ hàng 0 đến hết hàng thứ (r − 1) theo giả thiết quy nạp là 2(r−1)+1 + (r − 1) = 2r + (r − 1). Theo tính chất d) trong mục 1.2, ta thấy hàng thứ r có (2r + 1) phần tử, nên số các phần tử từ hàng 0 đến hết hàng r là 2r + (r − 1) + (2r + 1) = 2r+1 + r. - Theo giả thiết quy nạp, tổng tất cả các phần tử từ hàng 0 đến hết hàng thứ (r−1)+1 (r − 1) là 3 2 +1 + (r − 1). Theo tính chất (b) ở trên, tổng các phần tử ở hàng r là 3r + 1. Từ đó suy ra tổng tất cả các phần tử từ hàng 0 đến hết hàng thứ r là 3r+1 + 1 3r+1 + 1 r + (r − 1) + 3 + 1 = + r. 2 2 Mệnh đề được chứng minh. Tính chất 1.3.5. (a) Giá trị trung bình của các phần tử nằm trên hàng thứ r xấp xỉ bằng (3/2)r . Thực vậy, giá trị đó bằng (3r + 1)/(2r + 1) ' (3/2)n . 11 (b) Trên hàng thứ r ta luôn có phần tử thứ k bằng phần tử thứ (2r + 2 − k). Vì trên hàng thứ r có 2r + 1 phần tử; thấy ngay phần tử đầu tiên (ứng với k = 1) bằng phần tử cuối cùng 2r + 1 = 2r + 2 − 1. Từ đó suy ra phần tử thứ k bằng phần tử thứ 2r + 2 − k. (c) Trên hàng thứ r của mảng diatomic 1.2: phần tử xuất hiện là tổng của hai phần tử liền kề được gọi là phần tử cặp đôi bậc r, trên hàng thứ r có 2r−1 phần tử cặp đôi bậc r, và chúng đều ở các vị trí chẵn. Có 2r−1 + 1 phần tử không cặp đôi, các phần tử này đều là các số của hàng (r − 1) đưa xuống, và luôn ở vị trí lẻ trên hàng thứ r. Mệnh đề 1.3.6. Với 3 phần tử liền kề nhau (a, b, c) trên một hàng ta luôn có (a + c)/b là một số nguyên. Chứng minh. Thật vậy, có hai khả năng xảy ra, thứ nhất nếu b là phần tử cặp đôi, ta có ngay b = a + c nên (a + c)/b = 1. Thứ hai, trường hợp a và c là các phần tử cặp đôi, ta sẽ chứng minh bằng quy nạp theo chỉ số hàng. Với k = 3, có 4 phần tử cặp đôi, nên các bộ ba có dạng đó là: (4, 3, 5); (5, 2, 5); (5, 3, 4), cả ba trường hợp này tính chất này đều đúng (a + c)/b là số nguyên. Giả sử với k ≤ r − 1, mọi bộ ba (a, b, c), trong đó a và c là các số cặp đôi, ta luôn có: (a + c)/b là số nguyên. Xét trên hàng r, với bộ ba bất kì (a, b, c) mà a, c là các số cặp đôi. Kí hiệu p, a, b, c, q với a = p + b; c = b + q . Khi đó bộ ba (p, b, q) là ba phần tử liền nhau thuộc hàng (r − 1); theo giả thiết quy nạp ta có (p + q)/b là số nguyên. Vì vậy: a + c (b + p) + (b + q) 2b + p + q = = b b b là số nguyên. Ta có điều phải chứng minh. Nhận xét 1.3.7. Hai phần tử liền nhau bất kì trên một hàng là nguyên tố cùng nhau. Khẳng định này được suy ra từ tính chất h) trong mục 1.2. Mệnh đề 1.3.8. Mọi số cặp đôi bậc r đều là số Stern có chỉ số lẻ, nghĩa là: Nếu trên hàng thứ r, số a là số cặp đôi thì tồn tại k ∈ N sao cho a = S(2k+1). Chứng minh. - Trước hết ta sẽ chứng minh bằng quy nạp rằng: Phần tử đầu tiên của hàng thứ k là số Stern có chỉ số chẵn. Với k = 1, rõ ràng phần tử đầu tiên là 1 = S(2). Với k = 2, ta thấy phần tử đầu tiên là 1 = S(4). Giả sử mệnh đề đúng với k ≤ r − 1. 12 Theo cách xác định trong Bảng 1.3, thì hàng thứ (r − 1) có 2r−1 phần tử nằm trong dãy Stern S(n). Theo giả thiết quy nạp, phần tử đầu tiên của hàng đó có chỉ số chẵn, suy ra phần tử thứ 2r − 1 của hàng đó có chỉ số lẻ. Vì vậy phần tử đầu tiên của hàng thứ r có chỉ số chẵn. - Do vậy các số cặp đôi trên hàng thứ r là các số ở vị trí chẵn trên hàng đó (xuất phát từ số 1 là phần tử đầu hàng), Mà số 1 đó có chỉ số chẵn, nên các số cặp đôi có chỉ số lẻ. Mệnh đề 1.3.9. Cặp (a, b) hai phần tử liền nhau chỉ xuất hiện đúng một lần trong mảng diatomic. Chứng minh. - Trước hết, ta có nhận xét: Trong hai số liền nhau trên 1 hàng của mảng diatomic, số nào lớn hơn là số cặp đôi, và vì vậy số đó có chỉ số lẻ. - Ta chứng minh bằng phản chứng. Giả sử trong mảng diatomic, (a, b) là cặp số đầu tiên, mà cặp này lại xuất hiện ít nhất một lần trong các hàng sau đó. Nghĩa là tồn tại p và q (p < q) sao cho (a, b) = (S(p), S(p + 1)) = (S(q), S(q) + 1), trong đó p là số nguyên dương nhỏ nhất thỏa mãn điều kiện này. Giả sử a < b. Khi đó theo nhận xét trên b là số cặp đôi, suy ra tồn tại p1 để cho S(p) = S(2p1 ) = S(p1 ) = a và S(p+1) = S(2p1 +1) = S(p1 )+S(p1 +1) = b. Như vậy trong hàng thứ r có các số a, b = a + c, c mà a = S(p1 ), c = S(p1 + 1) = b − a. Hai phần tử (a, c) = (S(p1 ), S(p1 + 1)) nằm trên hàng thứ (r − 1). Lập luận tương tự đối với cặp (a, b) = (S(q), S(q +1)) ta cũng có b = S(q +1) là số cặp đôi nên tồn tại q1 sao cho : S(q) = S(2q1 ) = S(q1 ) = a, S(q + 1) = S(2q1 + 1) = S(q1 ) + S(q1 + 1) = b Nên sẽ có một cặp liền nhau trong mảng diatomic (S(q1 ), S(q1 + 1)) với S(q1 + 1) = b − a. Như vậy, tồn tại cặp (S(p1 ), S(p1 + 1)) với p1 < p, và cặp này cũng xuất hiện ít nhất một lần trong mảng diatomic. Điều này mâu thuẫn với giả thiết (a, b) = (S(p1 ), S(p1 + 1)) là cặp đầu tiên (p là số nguyên dương nhỏ nhất) ở trên. Ta có điều phải chứng minh. Mệnh đề 1.3.10. Giả sử a và b là 2 số nguyên dương, nguyên tố cùng nhau. Khi đó cặp (a, b) sẽ xuất hiện như 2 phần tử liền kề nhau trong dãy Stern hay nói cách khác, tồn tại k ∈ N sao cho (a, b) = (S(k), S(k + 1)). Chứng minh. Theo giả thiết ta có (a, b) = 1 hơn nữa theo thuật toán Euclide, ta có (a, b) = (a, b − a) = (a − b, b). Kí hiệu SEA là thuật toán cho cặp (a, b) 13 với (a, b − a) khi b ≥ a hoặc (a − b, b) khi a > b. Ta có nhận xét sau: Nếu cặp (a, b) không xuất hiện như hai phần tử liền nhau trong dãy Stern thì các cặp SEA (a, b) cũng không thuộc dãy Stern. Thực vậy, giả sử (a, b) = 1 , và cặp (a, b) không là hai phần tử liền nhau trong dãy Stern, thực hiện liên tục thuật toán SEA ta có: SEA SEA (a, b) −−→ · · · · · · −−→ (1, 1). Suy ra cặp (1,1) cũng không thuộc dãy Stern (vô lý, vì cặp (1, 1) là cặp đầu tiên trong dãy Stern). Nhận xét: Cho trước hai số bất kỳ a, b ∈ Z+ , (a, b) = 1, ta thấy cặp (a, b) luôn là một cặp liền nhau nào đó trong dãy Stern, ngoài ra đó là cặp duy nhất (tức là chúng chỉ xuất hiện đúng một lần trong dãy Stern). Vì vậy, ánh xạ ϕ : Z+ → Q+ xác định bởi ϕ(n) = S(n)/S(n + 1) là một song ánh. Từ đó ta có khẳng định sau. Định lý 1.3.11. Mọi số hữu tỷ dương đều có thể biểu diễn dưới dạng thương của hai số Stern liền nhau trong dãy Stern. Nghĩa là, mọi r ∈ Q+ tồn tại n ∈ N sao cho r = S(n)/S(n + 1). Vì S(2n) = S(n), nên bằng quy nạp ta có S(2k n) = S(n) do đó ta có S(2k ) = 1. Ta dễ dàng có Định lý 1.3.12. 1. Với 0 ≤ j ≤ 2r ta có S(2r n ± j) = S(2r − j)S(n) + S(j)S(n ± 1). (1.20) 2. Từ công thức (1.20) ta có S(2r − 1) = r và S(2r + 1) = r + 1. (1.21) 3. Theo định nghĩa ta cũng dễ thấy S(2n) < S(2n + 1) và S(2n + 2) < S(2n + 1). (1.22) 14 Chương 2 Về giá trị lớn nhất của dãy Stern 2.1 Giá trị lớn nhất trên một hàng của mảng diatomic của Stern Định nghĩa 2.1.1. Ký hiệu Lm (r) là giá trị lớn nhất thứ m trong hàng thứ r trong mảng diatomic của Stern. Nghĩa là giá trị lớn nhất trong hàng thứ r là L1 (r), giá trị lớn thứ hai là L2 (r), .... Kết quả sau đây được đề xuất bởi Lucas [6], sau đó được chứng minh bởi tác giả Lehmer [5]. Định lý 2.1.2. Với mọi r ≥ 0, ta có L1 (r) = Fr+2 . Ngoài ra, giá trị lớn nhất này xuất hiện với giá trị nr = (4.2r − (−1)r )/3, tương ứng như n∗r = (5.2r + (−1)r )/3. Chứng minh. • Xét trên mảng diatomic 1.2 ta thấy: Với r = 1, ta có F3 = 2 là một giá trị lớn nhất của hàng 1. Với r = 2, ta có F4 = 3 là giá trị lớn nhất của hàng 2, và ta có: n2 = 5, n∗2 = 7. Nghĩa là S(5) = S(7) = 3 = F4 là giá trị lớn nhất của hàng 2; Với r = 3; n3 = 11; n∗3 = 13, Ta có S(11) = S(13) = 5 = F5 là giá trị lớn nhất của hàng 3. Như vậy ta thấy định lý là đúng khi r = 1, r = 2 và r = 3. Hơn nữa ta còn nhận thấy bộ 3: (F4 , F5 , F3 ) và (F3 , F5 , F4 ) đều xuất hiện như bộ ba liền nhau trong hàng thứ 3, và F5 = F4 + F3 . 15 • Giả sử với mọi k ≤ r − 1, ta có phần tử lớn nhất của hàng thứ k là Fk+2 = Fk+1 + Fk và bộ 3: (Fk+1 , Fk+2 , Fk ), (Fk , Fk+2 , Fk+1 ) là liền kề nhau trong hàng thứ k. - Khi đó trong hàng thứ r có phần tử cặp đôi có dạng: Fr−2+1 + Fr−1+1 = Fr+1 + Fr = Fr+2 theo kí hiệu L1 (r) là phần tử lớn nhất của hàng r ta có Fr+2 ≤ L1 (r). - Mặt khác, do L1 (r) là phần tử cặp đôi bậc r nên trong hàng r có bộ ba (a, L1 (r), b) với a + b = L1 (r). Rõ ràng (a, b) là hai phần tử liền nhau của hàng (r − 1), khi đó một trong hai phần tử sẽ xuất hiện ở hàng thứ (r − 2). Vì vậy theo giả thiết quy nạp ta có: a + b ≤ L1 (r − 2) + L1 (r − 1) = Fr + Fr+1 = Fr+2 . Suy ra L1 (r) ≤ Fr+2 . Từ đó suy ra: L1 (r) = Fr+2 . - Vì giá trị lớn nhất của hàng thứ r xuất hiện xen kẽ bên trái, hoặc bên 4.2r − (−1)r phải giá trị lớn nhất của hàng trước đó, nên ta có nr = và 3 5.2r + (−1)r ∗ nr = . 3 Để ý rằng trong mảng diatomic của Stern, nằm trên hàng lẻ thì phần tử lớn nhất luôn nằm bên trái của phần tử lớn nhất của hàng trên đó, còn nếu trên hàng k chẵn thì phần tử lớn nhất luôn nằm bên phải của phần tử lớn nhất của hàng trên nó. Vì vậy, vị trí của phần tử lớn nhất của hàng thứ r được suy ra từ vị trí phần tử lớn nhất của hàng phía trên đó. nr = 2.nr−1 − (−1)r = 4.2r − (−1)r = . 3 Tương tự, ta có n∗r = 2[4.2r−1 − (−1)r−1 ] − (−1)r 3 5.2r + (−1)r . 3 16 Mối quan hệ giữa vị trí của giá trị lớn nhất trong hàng r và hàng thứ r − 1 đóng vai trò quan trọng. Ta có nr = 2nr−1 − (−1)r , (2.1) nghĩa là, giá trị lớn nhất trong hàng thứ r sẽ xuất hiện xen kẽ về bên trái hoặc bên phải của giá trị lớn nhất trước đó trong mảng diatomic. Tương tự, ta có n∗r = 2n∗r−1 + (−1)r (2.2) suy ra từ tính đối xứng trong nửa sau của hàng đó. Bảng 2.1: Giá trị lớn nhất của S(n) trong các hàng Hàng r n 2.2 L1 (r) 0 1 1 1 3 2 2 5,7 3 3 11,13 5 4 21,27 8 5 43,53 13 6 85,107 21 7 171,213 34 8 341,427 55 9 683,853 89 10 1365,1707 144 11 2731,3413 233 Giá trị lớn thứ hai trên mỗi hàng của mảng diatomic của Stern Chúng ta có thể tính toán giá trị lớn thứ hai trong một hàng cụ thể k ≤ 14 của mảng diatomic của Stern. Giá trị lớn thứ hai, là các giá trị được trình bày trong Bảng 2.2, và các giá trị này có mối quan hệ như sau L2 (r) = L2 (r − 1) + L2 (r − 2), với r ≥ 6. (2.3) 17 Bảng 2.2: Giá trị lớn thứ hai của S(n) trong các hàng Hàng r n L2 (r) 1 2, 4 1 2 6 2 3 9, 15 4 4 19, 23, 25, 29 7 5 45, 51 12 6 83, 91, 101, 109 19 7 173, 181, 203, 211 31 8 339, 363, 405, 429 50 9 685, 725, 811, 851 81 10 1363, 1451, 1621, 1709 131 11 2733, 2901, 3243, 3411 212 12 5459, 5803, 6485, 6829 343 Tuy nhiên, bắt đầu từ hàng thứ 4, tồn tại 4 giá trị lớn thứ hai. Hai trong 4 giá trị lớn thứ hai này sinh ra từ hai giá trị lớn thứ 2 của hai hàng liên tiếp phía trước, tức là L2 (r − 1) + L2 (r − 2), hai giá trị còn lại sinh ra từ tổ hợp tuyến tính 2L1 (r − 2) + L1 (r − 4). Định lý 2.2.1. Với mọi r ≥ 6 ta có L2 (r) = L2 (r − 1) + L2 (r − 2) = 2L1 (r − 2) + L1 (r − 4) = 2Fr + Fr−2 . Chứng minh. Ta chứng minh bằng quy nạp - Với r = 6 ta có L2 (6) = 19 = 12 + 7 = L2 (5) + L2 (4) = 2 × 8 + 3 = 2L1 (4) + L1 (2).Vậy định lý đúng với r = 6. - Giả sử định lý đúng với mọi chỉ số 6 ≤ k ≤ r − 1. Khi đó trên hàng thứ (r − 1) ta có bộ 3 liền nhau (L2 (r − 2), L2 (r − 1), L2 (r − 3)) với L2 (r − 1) = L2 (r − 2) + L2 (r − 3). Vì vậy trên hàng thứ r có phần tử A = L2 (r − 2) + L2 (r − 1). Theo giả thiết quy nạp ta có : A = L2 (r − 2) + L2 (r − 1) = 2L1 (r − 4) + L1 (r − 6) + 2L1 (r − 3) + L1 (r − 5) = 2Fr−2 + Fr−4 + 2Fr−1 + Fr−3 = 2(Fr−1 + Fr−2 ) + Fr−2 .