Luận văn Về giá trị lớn nhất của dãy stern

2 + (r − 1) + 3r + 1 = 3 r+1 + 1 2 + r. 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 = (b+ p) + (b+ q) b = 2b+ p+ q 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ó: (a, b) SEA−−→ · · · · · · SEA−−→ (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(2kn) = 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(2rn± 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.2 r − (−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 phải giá trị lớn nhất của hàng trước đó, nên ta có nr = 4.2r − (−1)r 3 và n∗r = 5.2r + (−1)r 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 = 2[4.2 r−1 − (−1)r−1] 3 − (−1)r = 4.2r − (−1)r 3 . Tương tự, ta có n∗r = 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 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 2.2 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. 18 Suy ra A = 2Fr + Fr−2. Theo Định lý 2.1.2, ta có L1(r) = Fr+2 = Fr+1 + Fr = 2Fr + Fr−1. Nên ta có A < L1(r) = Fr+2. Như vậy A không là phần tử lớn nhất của hàng r. Hay A ≤ L2(r). Với B < L1(r) trên hàng r, giả sử trên hàng r ta có bộ ba liền nhau là (a,B, b) với B = a+ b. Khi đó, trên hàng (r − 1), ta có cặp (a, b) liền nhau. Giả sử B là phần tử cặp đôi bất kỳ trên hàng r thỏa mãn B < L1(r). Ta sẽ chứng minh B ≤ A. Thật vậy, trên hàng r sẽ có bộ 3 liền nhau là (a,B, b), với B = a+ b. Trên hàng (r − 1) có cặp liền nhau (a, b). Có 2 khả năng xảy ra: • Khả năng 1. Một trong 2 phần tử đó là phần tử lớn nhất của hàng (r−1). Giả sử a = L1(r − 1). Theo Định lý 2.1.2, suy ra hoặc b = L1(r − 2), hoặc b = L1(r − 3). - Rõ ràng b 6= L1(r − 2), vì nếu ngược lại thì suy ra a + b = B = L1(r) trái với giả thiết ở trên về B. - Với khả năng b = L1(r − 3), ta có B = a+ b = L1(r − 1) + L1(r − 3) = Fr+1 + Fr−1 = Fr + Fr−1 + Fr−2 + Fr−3 = 2Fr + Fr−3 Vì với mọi r ≥ 6 ta có Fr−3 < Fr−2 suy ra B < A. • Khả năng 2. Cả 2 phần tử a và b đều không phải là phần tử lớn nhất của hàng (r − 1), suy ra a, b ≤ L2(r − 1). a) Trường hợp 1 trong 2 phần tử đó bằng L2(r− 1), rõ ràng trong hàng (r − 1) theo giả thiết quy nạp ta có 2 bộ 3 dạng: (L2(r − 2), L2(r − 1), L2(r− 3)) và (L1(r− 3)+L1(r− 5), L2(r− 1), L1(r− 3)). Giả sử a = L2(r − 1). Khi đó ∗ Nếu b = L2(r − 2) thì B = a+ b = A. ∗ Nếu b = L2(r − 3) thì B = a+ b < A ∗ Nếu b = L1(r−3)+L1(r−5) thì B = a+B = 3L1(r−3)+2L1(r− 5) = 3Fr−1 + 2Fr−3 = 2Fr + Fr−3 + Fr−5. Do Fr−2 = Fr−3 + Fr−4 suy ra B < A. Trường hợp b = L1(r − 3) hiển nhiên B < A. b) Xét trường hợp a, b < L2(r − 1). Giả sử a là phần tử cặp đôi bậc (r − 1). Khi đó b là phần tử nằm trên hàng (r − 2). Khi đó ta có 19 a < L2(r − 1) = 2Fr−1 + Fr−3 = Fr + 2Fr−3 và b ≤ L1(r − 2) = Fr. Do a là tổng của các số Fibonacci nên suy ra a ≤ Fr+Fr−3+Fr−4 = Fr + Fr−2. Do vậy B = a+ b ≤ 2Fr + Fr−2 = A. Ví dụ 2.2.2. Từ Bảng 2.2, ta xét hàng thứ 8, ta thấy S(363) = S(181) + S(182) = S(181) + S(91) = 31 + 19 = L2(7) + L2(6) = 50 = L2(8). Sử dụng Bảng 2.1, ta có S(339) = 2S(85) + S(84) = 2S(85) + S(21) = 2.21 + 8 = 2L1(6) + L1(4) = 50 = L2(8). Như vậy, cách thứ hai để thu được giá trị lớn thứ hai là từ 2L1(r − 2) + L1(r − 4), và nó sẽ xuất hiện hai lần từ bên trái hoặc bên phải vị trí L1(r). Ta có một cách tiếp cận nữa để tính toán giá trị lớn thứ hai trên một hàng. Định nghĩa 2.2.3. Với r ≥ 4, đặt n2,1(r) := 17 · 2r−2 − (−1)r−1 3 và n2,2(r) := 16 · 2r−2 − 7(−1)r 3 . Từ tính đối xứng đã được trình bày trong (1.19), ta có n∗2,1(r) = 19 · 2r−2 + (−1)r−1 3 và n∗2,2(r) = 20 · 2r−2 + 7(−1)r 3 . Ta thấy n2,1(r) = n2,2(r) = 35 tại r = 5 vì vậy chỉ tồn tại hai vị trí của L2(5). Ta thấy rằng S(n2,1(r)) và S(n ∗ 2,1(r)) cho ta hai giá trị lớn thứ hai trong hàng thứ r như tổng của các giá trị lớn thứ hai ở trên, và S(n2,2(r)) và S(n∗2,2(r)) chỉ ra giá trị lớn thứ hai của hàng thứ r như tổ hợp tuyến tính của các giá trị lớn nhất ở hàng trên. Ngoài ra n2,1(r) có dãy truy hồi tương tự nr trong (2.1): n2,1(r) = 17× 2r−2 − (−1)r−1 3 = 17× 2r−2 + 2× (−1)r−1 − 3× (−1)r−1 3 = 2n2,1(r − 1) + (−1)r. (2.4) Ta cũng có n2,2(r) = 16× 2r−2 − 7× (−1)r 3 = 4× 2 r − (−1)r 3 = 4nr−2 − (−1)r = nr − 2(−1)r. (2.5) 20 đẳng thức này 2L1(r− 2) +L1(r− 4), sẽ xuất hiện hoặc từ hai phía bên trái hoặc bên phải của L1(r) xuất hiện trong hàng. Với các kết quả trên ta sẽ chỉ ra một cách chứng minh khác của Định lý 2.2.1. Định lý 2.2.4. (i) L2(r) = Fr+2 − Fr−3 = L1(r)− Fr−3, với r ≥ 4. (ii) S(n2,1(r)) = S(n ∗ 2,1(r)) = S(n2,2(r)) = S(n ∗ 2,2(r)) = L2(r), với r ≥ 4. (iii) Với r ≥ 6, ta có S(n2,1(r)) = S(n∗2,1(r)) = L2(r) = L2(r−1)+L2(r−2), tức là dãy các giá trị lớn thứ 2 hoàn toàn được xác định từ tổng L2(r − 1) + L2(r − 2) với r ≥ 6. (iv) Với r ≥ 8 ta có S(n2,2)(r) = S(n∗2,2(r)) = L2(r) = 2L1(r−2)+L1(r−4). Chứng minh. Giả sử các khẳng định (i)–(iv) đúng với tất cả các hàng có chỉ số k ≤ r với r ≥ 8. Trước tiên ta sẽ chứng minh rằng, ngoài giá trị lớn nhất trong hàng r + 1, không tồn tại số hạng nào lớn hơn L2(r) + L2(r − 1). Nếu 2k ∈ [2r+1, 2r+2], khi đó theo giả thiết quy nạp từ khẳng định (i), ta thấy tất cả các số hạng chẵn trong hàng (r + 1) có S(2k) = S(k) ≤ L1(r) = Fr+2 < Fr+2 + 2Fr−1 = Fr+3 − Fr−2 = L2(r) + L2(r − 1). Tiếp theo ta sẽ chỉ ra cận trên của tất cả các số hạng lẻ của hàng thứ (r+1), đặc biệt là các số hạng S(4k±1). Ta xét k ∈ [2r−1, 2r] sao cho 4k±1 ∈ (2r+1, 2r+2). Trước tiên ta xét một số trường đặc biệt. Nếu k = nr−1, hoặc k = n∗r−1, ta có S(2nr−1 − (−1)r) = S(nr) = L1(r) = S(n∗r) = S(2n∗r−1 + (−1)r), suy ra S(2nr−1 + (−1)r) < L1(r) và S(2n∗r−1 − (−1)r) < L1(r). Tương tự, nếu k = 2nr−2 hoặc k = 2n∗r−2, ta có S(2 · 2nr−2 + (−1)r) = S(nr) = L1(r) = S(n∗r) = S(2 · 2n∗r−2 − (−1)r), nghĩa là S(2 · 2nr−2 − (−1)r) < L1(r) và S(2 · 2n∗r−2 + (−1)r) < L1(r). Ngoại trừ các trường hợp đặc biệt k = nr−1, n∗r−1, 2nr−2, hoặc 2n ∗ r−2, ta có S(2k ± 1) < L1(r), vì vậy S(2k ± 1) ≤ L2(r). Khi đó ta có S(4k ± 1) = S(2k) + S(2k ± 1) = S(2k ± 1) + S(k) ≤ L2(r) + L2(r − 1). 21 Tiếp theo ta xét tiếp các trường hợp sau. Nếu k = nr−1, ta có S(4nr−1 − (−1)r) = S(2nr−1) + S(2nr−1 − (−1)r) = S(nr−1) + S(nr) = L1(r + 1), ta bỏ qua giá trị lớn nhất này (vì ta tìm giá trị lớn thứ hai). Tiếp theo ta có S(4nr−1 + (−1)r) = S(2nr−1) + S(2nr−1 + (−1)r) = S(nr−1) + S(nr−1) + S(nr−1 + (−1)r) = 2S(nr−1) + S(2nr−2 + 2(−1)r) = 2S(nr−1) + S(nr−2 + (−1)r) = 2S(nr−1) + S(2nr−3 − (−1)r + (−1)r) = 2S(nr−1) + S(nr−3) = 2L1(r − 1) + L1(r − 3). (2.6) Từ tính đối xứng, ta có S(4n∗r−1 − (−1)r) = 2L1(r − 1) + L1(r − 3) và S(4n∗r−1 + (−1)r) = L1(r). Cuối cùng, nếu k = 2nr−2 ta có S(4 · 2nr−2 ± 1) = 2S(nr−2) + S(2nr−2 ± 1) = { 2S(nr−2) + S(2nr−2 + (−1)r) 2S(nr−2) + S(2nr−2 − (−1)r) = { 2S(nr−2 + S(nr−1) = 2L1(r − 2) + L1(r − 1) 3S(nr−2) + S(nr−4) = 3L1(r − 2) + L1(r − 4) < 2L1(r − 1) + L1(r − 3). Vì vậy ta chỉ cần so sánh 2L1(r − 1) + L1(r − 3) với L2(r) + L2(r − 1). Tuy nhiên, sử dụng giả thiết quy nạp trong phần (i) ta có L2(r) + L2(r − 1) = Fr+2 − Fr−3 + Fr+1 − Fr−4 = Fr+3 − Fr−2 = L1(r + 1)− L1(r − 4) = 2L1(r − 1) + L1(r − 3). Vì vậy, tất cả các phần tử trong hàng thứ (r+ 1), ngoài giá trị lớn nhất, nhỏ hơn hoặc bằng L2(r) + L2(r − 1), do đó ta có L2(r + 1) = Fr+3 − Fr−2 = L2(r) + L2(r − 1) = 2L1(r − 1) + L1(r − 3). 22 Đánh giá S(n2,1(r + 1)) và sử dụng đẳng thức (2.4), ta có S(n2,1(r + 1)) = S(2n2,1(r) + (−1)r+1) = S(n2,1(r)) + S(n2,1(r)− (−1)r) = S(n2,1(r)) + S(2n2,1(r − 1)) = S(n2,1(r)) + S(n2,1(r − 1)) = L2(r) + L2(r − 1). Ta cũng thấy rằng từ đẳng thức (2.5) ta có n2,2(r + 1) = 4nr−1 + (−1)r, và trong đánh giá từ đẳng thức (2.6) ta đã có S(4nr−1+(−1)r) ta cũng có L2(r). Do đó, ta thu được giá trị lớn nhất thứ hai. Cuối cùng, bằng tính đối xứng của dãy Stern trong các hàng, ta có S(n∗2,1(r+1)) = S(n2,1(r+1)) = L2(r+1) = S(n2,2(r+1)) = S(n ∗ 2,2(r+1)). 2.3 Giá trị lớn thứ ba trên mỗi hàng của mảng diatomic của Stern Giá trị lớn thứ ba trong các hàng của mảng diatomic, được cho trong Bảng 2.3, cũng thỏa mãn dãy truy hồi Fibonacci. Sự lặp lại này bắt đầu ở hàng thứ 10 và các hàng 8 và 9 cho hai giá trị ban đầu Tương tự với giá trị lớn thứ hai trong mỗi hàng, tồn tại bốn phần từ bằng nhau lớn thứ ba. Theo tính đối xứng, thì hai phần tử thứ ba trên mỗi hàng có dạng L3(r − 1) + L3(r − 2) và hai phần tử còn lại có dạng (2L1(r−4)+L1(r−6))+(3L1(r−4)+2L1(r−6)) hay 5L1(r−4)+3L1(r−6) Định nghĩa 2.3.1. Với r ≥ 8, xét n3,1(r) := 64 · 2r−4 − 31(−1)r 3 và n3,2(r) := 65 · 2r−4 + (−1)r 3 . Bằng tính đối xứng, ta có n∗3,1(r) = 80 · 2r−4 + 31(−1)r 3 và n∗3,2(r) = 79 · 2r−4 − (−1)r 3 . Ta sẽ chứng minh rằng n3,1(r), n ∗ 3,1(r), n3,2(r), và n ∗ 3,2(r) cho ta giá trị lớn thứ ba trong hàng thứ r của mảng diatomic. Từ đó, ta có n3,1(r) = 4 · 2r − (−1)r − 30(−1)r 3 = nr − 10(−1)r. (2.7) n3,2(r) = 2n3,2(r − 1) + (−1)r và n3,2(r)− (−1)r = 2n3,2(r − 1). (2.8) 23 Bảng 2.3: Giá trị lớn thứ ba trong các hàng của mảng diatomic của Stern Hàng r n L3(r) 1 N/A N/A 2 4 1 3 10, 14 3 4 17, 22, 26, 31 5 5 37, 41, 55, 59 11 6 75, 87, 105, 117 18 7 165, 219 30 8 331, 347, 421, 437 49 9 693, 843 80 10 1355, 1387, 1685, 1717 129 11 2741, 2773, 3371, 3403 209 12 5451, 5547, 6741, 6837 338 Định lý 2.3.2. (i) Với r ≥ 8, L3(r) = L2(r) − Fr−7 = Fr+1 + 5Fr−4 = L1(r)− 3Fr−5. (ii) Với r ≥ 8, S(n3,1(r)) = S(n∗3,1(r)) = S(n3,2(r)) = S(n∗3,2(r)) = L3(r). (iii) Với r ≥ 8, S(n3,1(r)) = S(n∗3,1(r)) = L3(r) = 5L1(r − 4) + 3L1(r − 6). (iv) Với r ≥ 10, S(n3,2(r)) = S(n∗3,2(r)) = L3(r) = L3(r − 1) + L3(r − 2). Chứng minh. Ta sẽ chứng minh quy nạp theo chỉ số dãy k ≥ 10. 1. Khi k = 10. Căn cứ vào các bảng (2.1), (2.2), và (2.3) và dãy Fibonacci ta có: (a) L3(10) = 129 = 131− 2 = L2(10)− F3 = L2(10)− F10−7 = 89 + 5× 8 = F10+1 + 5F10−4 = 144− 3× 5 = L1(10)− 3F10−5 (b) n3,1(10) = 1355;n ∗ 3,1(10) = 1717 n3,2(10) = 1387;n ∗ 3,2(10) = 1685 và S(1355) = S(1717) = S(1387) = S(1685) = 129 = L3(10). 24 (c) L3(10) = 129 = 5.21 + 3.8 = 5.L1(10− 4) + 3L1(10− 6) (d) L3(10) = 80 + 49 = L3(10− 1) + L3(10− 2) Như vậy với k = 3, các điều kiện i), ii), iii), iv) đều đúng. 2. Giả sử định lý đúng với mọi k : 10 ≤ k ≤ r. Ta sẽ chứng minh định lý đúng với k = r + 1 (a) Trước hết sử dụng biểu thức (2.8) ta có: S(n3,2(r + 1)) = S(2n3,2(r)− (−1)r) = S(n3,2(r)) + S(n3,2(r)− (−1)r) = L3(r) + S(2n3,2(r − 1)) = L3(r) + L3(r − 1). (b) Tiếp theo sử dụng biểu thức (2.7) ta có: S(n3,1(r + 1)) = S(nr+1 + 10(−1)r) = S(2nr + (−1)r + 10(−1)r) = S(nr + 5(−1)r) + S(nr + 5(−1)r + (−1)r) = S(2nr−1 − (−1)r + 5(−1)r) + S(2nr−1 + 6(−1)r − (−1)r) = S(nr−1 + 2(−1)r) + S(nr−1 + 3(−1)r) + S(nr−1 + 3(−1)r − (−1)r) = 2S(nr−1 + 2(−1)r) + S(nr−1 + 3(−1)r) = 2S(2nr−2 + (−1)r + 2(−1)r) + S(2nr−2 + (−1)r + 3(−1)r) = 2S(nr−2 + (−1)r) + 2S(nr−2 + 2(−1)r) + S(nr−2 + 2(−1)r) = 2S(nr−3) + 3S(2nr−3 + (−1)r) = 2S(nr−3) + 3S(nr−3) + 3S(nr−3 + (−1)r) = 5S(nr−3) + 3S(2nr−4 + 2(−1)r) = 5S(nr−3) + 3S(nr−4 + (−1)r) = 5S(nr−3) + 3S(2nr−5) = 5L1(r − 3) + 3L1(r − 5). (c) Cũng từ giả thuyết quy nạp cho điều kiện i) ta có: A = L3(r) + L3(r − 1) = Fr+3 − 3Fr−4 = 5Fr−1 + 3Fr−3 = 5L1(r − 3) + 3L1(r − 5). 25 (d) Ta sẽ chứng minh trong hàng (r + 1) của mảng diatomic của Stern, tất cả các phần tử ngoại trừ L1(r+1) và L2(r+1) đều nhỏ hơn hoặc bằng A. Ta thấy với mọi số chẵn 2m ∈ [2r+1, 2r+2], theo các tính chất đã chỉ ra của mảng diatomic thì các số Stern S(2m) không là các số cặp đôi, vì vậy chúng đều thuộc hàng thứ r. Do vậy ta có: S(2m) = S(m) ≤ L1(r) = Fr+2 ≤ Fr+2 + 5Fr−3 = L3(r) + L3(r − 1) = A. Tiếp theo xét các phần tử S(2m+ 1) với 2m+ 1 ∈ [2r+1, 2r+2], trong số các phần tử S(2m+1) trên hàng (r+1) này trước hết ta loại bỏ đi (xóa đi) 2 phần tử lớn nhất (L1(r + 1)) và 4 phần tử lớn thứ hai (L2(r + 1)) của hàng này. Ta sẽ chứng minh mọi phần tử còn lại dạng S(2m+1) của hàng (r + 1) đều ≤ A. Theo Mệnh đề 1.3.8 trong 1.3, ta thấy S(2m + 1) đều là các số cặp đôi bậc (r + 1) và ta có: S(2m+ 1) = S(m) + S(m+ 1), trong đó các phần tử S(m) và S(m + 1) là 2 phần tử liền nhau của hàng thứ r. Ký hiệu b là phần tử lớn hơn, và c là phần tử bé hơn trong 2 phần tử S(m) và S(m+1). Ta thấy b là phần tử cặp đôi bậc r, và c là phần tử thuộc hàng (r − 1). Để chứng minh: S(2m + 1) = b + c ≤ A, ta lần lượt xét từng trường hợp dưới đây: (a) Trường hợp b = L1(r), khi đó c = L1(r − 1) hoặc c = L1(r − 2) vì L1(r) + L1(r − 1) = L1(r + 1) là phần tử lớn nhất của hàng (r + 1), nên ta loại bỏ khả năng c = L1(r − 1), vì ta đã loại đi phần tử lớn nhất. Khi c = L1(r − 2) ta có: b+ c = L1(r) + L1(r − 2) = Fr+2 + Fr = Fr+2 + 3Fr−3 + Fr−4 < Fr+2 + 5Fr−3. Suy ra khi b = L1(r) ta có S(2m+ 1) = b+ c < A. (b) Trường hợp b = L2(r) khi đó c nhận một trong 4 giá trị sau: c = L2(r − 1) hoặc c = L2(r − 2); hoặc c = L1(r − 2) + L1(r − 4) hoặc c = L1(r − 2). i. Với c = L2(r − 1)⇒ b+ c = L2(r) + L2(r − 1) = L2(r + 1), điều này không xảy ra, vì ta đã loại bỏ phần tử L2(r + 1). 26 ii. Với c = L2(r − 2) theo Định lý 2.2.4 ta có: S(2m+ 1) = b+ c = L2(r) + L2(r − 2) = Fr+2 − Fr−3 + Fr − Fr−5 = Fr+2 + Fr−2 + 2Fr−4 = Fr+2 + Fr−3 + 3Fr−4 < Fr+2 + 5Fr−3 = A. iii. Với c = L1(r − 2) + L1(r − 4) ta có b+ c = 2L1(r − 2) + L1(r − 4) + L1(r − 2) + L1(r − 4) = 3L1(r − 2) + 2L1(r − 4) = 3Fr + 2Fr−2 = Fr+2 + 3Fr−2 = Fr+2 + 3Fr−3 + 3Fr−4 = Fr+2 + 4Fr−3 + Fr−4 + Fr−6 < Fr+2 + 5Fr−3 = A. iv. Trường hợp c = L1(r − 2), hiển nhiên b+ c < A. (c) Trường hợp b = L3(r). Theo giả thiết quy nạp có 2 cách để xác định L3(r), vì vậy c có thể nhận một trong 4 giá trị sau: c = L3(r − 1), hoặc c = L3(r − 2), hoặc c = 2L1(r − 4) + L1(r − 6) hoặc c = 3L1(r − 4) + 2L1(r − 6). i. Với c = L3(r − 1). Ta có b+ c = L3(r) + L3(r − 1) = A. ii. Với c = L3(r − 2), hiển nhiên b+ c < A. iii. Với c = 3L1(r − 4) + 2L1(r − 6). Ta có b+ c = 8L1(r − 4) + 5L1(r − 6) = 8Fr−2 + 5Fr−4 < A. iv. Trường hợp c = 2L1(r − 4) + L1(r − 6) hiển nhiên b+ c < A. (d) Trường hợp b < L3(r). i. Với c = L1(r − 1) = Fr+1 là phần tử lớn nhất trên hàng (r − 1). Khi đó hoặc b = L1(r − 1) + L1(r − 2) = L1(r), ta loại bỏ trường hợp này vì b < L3(r). Hoặc b = L1(r − 1) + L1(r − 3), khi đó b+ c = 2L1(r − 1) + L1(r − 3) = L2(r + 1), điều này cũng không xảy ra vì ta đã loại các phần tử lớn thứ 2 khỏi hàng (r + 1). ii. Với c = L2(r − 1). Khi đó b có thể nhận một trong 4 giá trị sau: • Với b = L2(r−1)+L2(r−2) = L2(r). Ta loại bỏ khả năng này vì đang xét trường hợp b < L2(r). • Với b = L2(r − 1) + L2(r − 3), Khi đó b+ c = 2L2(r − 1) + L2(r − 3) = 2Fr+1 − 2Fr−4 + Fr−1 − Fr−6 = Fr+2 + 4Fr−3 − Fr−6 < Fr+2 + 5Fr−3 = A. 27 • Với b = 3L1(r − 3) + 2L1(r − 5), vì c = L2(r − 1) = 2L1(r − 3) + L1(r − 5) ta có b+ c = 5L1(r − 3) + 3L1(r − 5) = 5Fr−1 + 3Fr−3 = Fr+2 + 5Fr−3 = A • b = 3L1(r − 3) + L1(r − 5), hiển nhiên b+ c < A. iii. Với c ≤ L3(r − 1), ta có b+ c < L3(r) + L3(r − 1) = A. Như vậy trong mọi khả năng lựa chọn các giá trị b và c ta luôn có S(2m+ 1) = b+ c ≤ A = L3(r) + L3(r − 1). Vậy A là phần tử lớn thứ 3 trong hàng (r + 1) hay L3(r + 1) = L3(r) + L3(r − 1). Định lý được chứng minh. Nhận xét 2.3.3. Theo các Định lý 2.2.4 (i) và 2.3.2 (i), ta có L2(r) = Fr+2−Fr−3 và L3(r) = L2(r)−Fr−7. Chú ý rằng L3(r) = Fr+2−Fr−3−Fr−7. Từ Bảng 2.4, ta có các chú ý sau: L4(r) = L3(