Luận văn Thạc sĩ Toán học: Dãy diatomic của Stern

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

26
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Năm 1858 Moritz Abraham Stern (M.A. Stern) đã đưa ra định nghĩa mảng diatomic (trong bài báo "Ueber eine zahlentheoretische Funktion", Journal fur die reine und angewandte Mathematik, 55:193–220), đây là một khái niệm toán học có nhiều tính chất hay tương tự tam giác Pascal, từ mảng diatomic, Stern đã xây dựng nên dãy diatomic, trong đó có chứa các phần tử của dãy Fibonacci... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Dãy diatomic của Stern

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGÔ THỊ VÂN ANH DÃY DIATOMIC CỦA 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——————– NGÔ THỊ VÂN ANH DÃY DIATOMIC CỦA STERN 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ố: 8460113 NGƯỜI HƯỚNG DẪN KHOA HỌC (Xác nhận) PGS. TS. Nông Quốc Chinh THÁI NGUYÊN, 11/2018
1 Mục lục Bảng ký hiệu 2 Mở đầu 3 Chương 1. Mảng diatomic và dãy diatomic của Stern 5 1.1 Các kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Một số định nghĩa . . . . . . . . . . . . . . . . . . . 5 1.1.2 Dãy Fibonacci . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Dãy Jacobsthal . . . . . . . . . . . . . . . . . . . . 9 1.1.4 Hệ cơ số . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Mảng diatomic của Stern . . . . . . . . . . . . . . . . . . . 14 1.3 Dãy diatomic của Stern . . . . . . . . . . . . . . . . . . . . 18 Chương 2. Các tính chất của dãy diatomic và mảng diatomic của Stern 23 2.1 Biểu diễn siêu nhị phân của một số tự nhiên . . . . . . . . 23 2.2 So sánh với tam giác Pascal . . . . . . . . . . . . . . . . . . 25 2.3 Mô tả tập số hữu tỉ qua dãy Stern . . . . . . . . . . . . . . 32 Chương 3. Ứng dụng của dãy diatomic và mảng diatomic của Stern 38 3.1 Số hợp lý Stern trung bình . . . . . . . . . . . . . . . . . . 38 3.2 Cặp Stern, mod d . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Hàm Minkowski . . . . . . . . . . . . . . . . . . . . . . . . 43 Kết luận 46 Tài liệu tham khảo 47
2 Bảng ký hiệu N Tập hợp các số tự nhiên Z Tập hợp các số nguyên Z Tập hợp các số nguyên dương Q Tập hợp các số hữu tỉ Q Tập hợp các số hữu tỉ dương
3 Mở đầu Năm 1858 Moritz Abraham Stern (M.A. Stern) đã đưa ra định nghĩa mảng diatomic (trong bài báo "Ueber eine zahlentheoretische Funktion", Journal f¨ ur die reine und angewandte Mathematik, 55:193–220), đây là một khái niệm toán học có nhiều tính chất hay tương tự tam giác Pascal, từ mảng diatomic, Stern đã xây dựng nên dãy diatomic, trong đó có chứa các phần tử của dãy Fibonacci. . . Mục tiêu của luận văn là trình bày những vấn đề cơ bản của mảng diatomic và dãy diatomic của Stern, nghiên cứu một số tính chất của nó và đưa ra một vài ứng dụng của dãy Stern trên cơ sở nội dung của hai tài liệu là: [1] Sam Northshield (2010), “Stern’s Diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4,. . . ”, Amer. Math. Monthly, 177, pp. 581–598; và [2] Bruce Reznick (2008), “Regularity Properties of the Stern Enumeration of the rationals”, Journal of Integer Sequence, Vol.11. 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 3 chương. Chương 1: Mảng diatomic và dãy diatomic của Stern. Chương này trình bày một số kiến thức cơ bản về ước số, “thuật toán Euclid” và “thuật toán Euclid chậm” để tìm ước chung lớn nhất của hai số nguyên dương; dãy fibonacci; dãy Jacobsthal; khái niệm và một số nhận xét, tính chất của mảng diatomic và dãy diatomic của Stern. Chương 2: Các tính chất của dãy diatomic và mảng diatomic của Stern. Chương này trình bày cách biểu diễn siêu nhị phân của một số nguyên, so sánh với tam giác Pascal và mô tả các tập số hữu tỉ qua dãy Stern. Chương 3: Ứng dụng của dãy diatomic và mảng diatomic của
4 Stern. Chương này trình bày một số ứng dụng của mảng diatomic và dãy diatomic của Stern. Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và giúp đỡ của PGS.TS. Nông Quốc Chinh. Thầy đã giành nhiều thời gian chỉ bảo tận tình, hướng dẫn và giải đáp các thắc mắc của tôi. Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến Thầy. Tôi xin gửi lời cảm ơn tới các quý thầy, cô khoa Toán - Tin và phòng Đào tạo của trường Đại học Khoa học - Đại học Thái Nguyên, cũng như các thầy, cô tham gia giảng dạy khóa cao học 2016-2018 đã tận tình chỉ bảo, 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. Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên giúp đỡ, là chỗ dựa vững chắc về vật chất và tinh thần cho tôi trong suốt quá trình học tập và hoàn thiện luận văn Thạc sĩ. Mặc dù đã có nhiều cố gắng, nhưng luận văn vẫn còn một số hạn chế nhất định. Kính mong thầy cô và các bạn góp ý để tác giả tiếp tục hoàn thiện luận văn này. Thái Nguyên, tháng 10 năm 2018 Người viết luận văn Ngô Thị Vân Anh
5 Chương 1 Mảng diatomic và dãy diatomic của Stern 1.1 Các kiến thức chuẩn bị 1.1.1 Một số định nghĩa Định nghĩa 1.1.1. Cho a, b P Z, b 0. Ta nói a chia hết cho b, hoặc a là bội của b, hoặc b là ước của a khi và chỉ khi tồn tại số nguyên q sao cho a b.q. Khi đó ta viết: b | a hay a .. b để chỉ rằng a chia hết cho b. . Số nguyên dương c lớn nhất là ước của cả hai số nguyên a, b được gọi là ước số chung lớn nhất (ƯCLN) của a và b. Ký hiệu ước chung lớn nhất của a và b là: gcdpa, bq hay pa, bq. Chú ý : Trong trường hợp cả hai số nguyên a và b đều bằng 0 thì chúng không có ƯCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của a và b. Nếu chỉ một trong hai số a hoặc b bằng 0, số kia khác 0 thì ƯCLN của chúng bằng giá trị tuyệt đối của số khác 0. Ví dụ 1.1.2. p12, 36q 12; p5, 0q 5. Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Ta viết: pa, bq 1. Ví dụ 1.1.3. p9, 58q 1 nên 9 và 58 là nguyên tố cùng nhau.
6 Định nghĩa 1.1.4. Cho hai số dương: a là số bị chia và b là số chia, a modulo b kí hiệu là a mod b là số dư của phép chia của a cho b. Ví dụ 1.1.5. “8 mod 3” bằng 2 vì 8 chia cho 3 có thương số là 2 và số dư là 2. Định nghĩa 1.1.6. Cho hai số nguyên dương a, b (với a ¡ b). Thuật toán Euclid để tìm ước chung lớn nhất của hai số nguyên dương a, b được thực hiện như sau. Bước 1: Chia a cho b được q0 và dư r1 nghĩa là a q0 b r1 , 0 ¤ r1 b. Nếu r1 0 thì dừng lại. Nếu r1 0 thì tiếp tục thực hiện bước 2. Bước 2: Chia b cho r1 được q1 và dư r2 nghĩa là b q1 r1 r2 , 0 ¤ r2 r1 . Nếu r2 0 thì dừng lại. Nếu r2 0 thì tiếp tụcthực hiện bước 3. ... Bước k : Chia rk2 cho rk1 được qk1 và dư rk nghĩa là rk2 qk1 rk1 rk , 0 ¤ rk rk1 . ... Bước m pm ¡ k q: Chia rm2 cho rm1 được qm1 nghĩa là rm2 qm1 rm1 . Sau mỗi bước các số dư đều thực sự giảm nên đến bước thứ m nào đó, quá trình sẽ dừng lại khi phép chia đó có số dư bằng 0. Ta có: pa, bq pb, r1 q pr1 , r2 q . . . prk1 , rk2 q . . . rm1 . Do đó: pa, bq rm1 Ví dụ 1.1.7. Áp dụng thuật toán Euclid để tìm p3484, 3276q. Ta có
7 Vậy p3484, 3276q p3276, 208q p208, 156q p156, 52q 52. Định nghĩa 1.1.8. Cho hai số nguyên dương a, b. Thuật toán Euclid chậm để tìm ước chung lớn nhất của hai số nguyên dương a, b được thực hiện như sau: trừ số lớn cho số nhỏ hơn ta được cặp số mới là kết quả phép trừ và số nhỏ, lặp lại và dừng khi hai số trong cặp bằng nhau. Ta nhận thấy rằng, sau mỗi bước, ước chung lớn nhất của hai số a và b là không đổi. Thật vậy, giả sử a và b là hai số nguyên dương (a ¡ b), k là ước chung lớn nhất của a và b thì a a1 k, b b1 k . Khi đó, a b pa1 b1 qk , ở đây a1 , b1 là hai số nguyên tố cùng nhau, từ đây suy ra ước chung lớn nhất của b và a b cũng là k . Vì tập số tự nhiên bị chặn dưới bởi số 0, nên thuật toán này sẽ kết thúc sau một số hữu hạn bước và vì ước chung lớn nhất được giữ nguyên ở mỗi bước, nên thuật toán phải kết thúc tại rk, k s, ở đó k pa, bq. Giả sử có cặp ra, bs, b ¡ a, ta ký hiệu thuật toán Euclid chậm là SEA, và viết: ra, bs ÝÝÝÑ ra, b as. SEA Ví dụ 1.1.9. Áp dụng thuật toán Euclid chậm để tìm p4, 7q và p16, 28q. r4, 7s ÞÑ r4, 3s ÞÑ r1, 3s ÞÑ r1, 2s ÞÑ r1, 1s . Vậy p4, 7q 1. r16, 28s ÞÑ r12, 16s ÞÑ r4, 12s ÞÑ r4, 8s ÞÑ r4, 4s . Vậy p16, 28q 4. 1.1.2 Dãy Fibonacci Định nghĩa 1.1.10. Dãy số Fibonacci, ký hiệu pFn q, được định nghĩa bởi công thức truy hồi như sau: $ ' ' &F0 0 F1 1 ' ' n 1 Fn pn ¥ 1q. %F Fn 1 Theo định nghĩa ta có dãy Fibonaci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
8 Số hạng tổng quát của dãy Fibonacci được xác định bởi công thức Binet: ? n ? n Fn 1 ? 1 5 5 φn φ n φφ (1.1) 2n 5 ? ? 1 5 trong đó φ và φ 1 5 . 2 2 Một vài tính chất của dãy Fibonaci: Tính chất 1.1.11. Với số nguyên dương n bất kỳ ta có:pFn , Fnq 1. 1 Tính chất 1.1.12. Với hai số nguyên dương m, n bất kỳ, nếu n | m thì Fn | F m . Mệnh đề 1.1.13. Với hai số nguyên dương m, n bất kỳ ta có đẳng thức: Fm Fm1.Fn 1 Fm.Fn. n (1.2) Chứng minh. Qui nạp theo n, với n 1 đúng. Giả sử (1.2) đúng với n k tức là Fm k Fm1 .Fk 1 Fm .Fk , ta chứng minh: Fm k 1 Fm1.Fk 2 Fm .Fk 1 . Thật vậy, ta có: Fm k 1 Fm k 1 Fm k Fm1.Fk Fm.Fk1 Fm1 .Fk 1 Fm .Fk Fm1. pFk Fk 1q Fm . pFk1 Fk q Fm1.Fk 2 Fm.Fk 1. Vậy theo nguyên lí qui nạp ta có điều phải chứng minh. Cho m kn thì ta suy ra thêm được một số tính chất sau: Tính chất 1.1.14. Nếu Fn chia hết cho Fm thì n chia hết cho m pm ¡ 2q. Tính chất 1.1.15. Với hai số nguyên dương m, n bất kỳ ta có: pFm, Fnq Fpm,nq. Tính chất 1.1.16. n ¥ 5 và Fn là số nguyên tố thì n cũng là số nguyên tố.
9 Tính chất 1.1.17. pFn q chứa vô hạn những số nguyên tố đôi một cùng nhau. Tính chất 1.1.18. Với số nguyên n ¥ 1 ta có: F5n 5Fnqn, qn không chia hết cho 5. Tính chất 1.1.19. Với số nguyên n ¥ 1 ta có: Fn pFn1 Fn 1q . F2n Tính chất 1.1.20. Với số nguyên n ¥ 1 ta có: F2n 1 Fn1 Fn 1 Fn Fn 2 . Tính chất 1.1.21. Với số nguyên n ¥ 1 ta có: F2n 1 Fn 1 Fn 2 Fn1 Fn . Tính chất 1.1.22. Với mọi số nguyên không âm n ta có: Fn 2 Fn 1 2 . F2n 1 Tính chất 1.1.23. Với số nguyên n ¥ 1 ta có: Fn Fn 1 Fn1 Fn 2 p1qn1 . 1.1.3 Dãy Jacobsthal Định nghĩa 1.1.24. Dãy Jacobsthal pJn q là dãy được định nghĩa bởi công thức truy hồi sau: $ ' ' &J0 0 J1 1 ' ' n 1 Jn 2Jn1 , n 1, 2, 3, . . . %J Một số số hạng đầu tiên của dãy Jacobsthal là: 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, . . . Mệnh đề 1.1.25. Số hạng tổng quát của dãy Jacobsthal được xác định bởi công thức Binet 2n p1qn Jn . (1.3) 3
10 Chứng minh. Thật vậy, với n 1 thì J1 1 (đúng). Giả sử (1.3) đúng với n, ta sẽ chứng minh cho (1.3) đúng với n 1, tức là phải chứng minh: 2n 1 p1qn 1 Jn 1 . 3 Ta có, 2n p1qn 2n1 p1qn1 Jn 1 Jn 2Jn1 3 2. 3 2.2 p1q n n 2.p1q n 3 2 n 1 p1qn 3 2 n 1 p1q p1qn 3 2 n 1 p1qn 1 . 3 Nhận xét 1.1.26. Vì số hạng Jn của dãy Jacobsthal là số nguyên nên từ công thức (1.3) suy ra Jn luôn là một số lẻ. Mệnh đề 1.1.27. Dãy Jacobsthal pJn q có: Jn 2Jn1 p1qn1. Chứng minh. Từ công thức (1.3) ta có 2n p1qn 2n1 p1qn1 Jn 2Jn1 2. 3 3 n 1 2.p1q 3 p1q n 2p1qn1 p1q p1qn1 3 n 1 p1q . 1.1.4 Hệ cơ số Định lý 1.1.28. Cho b và k là những số tự nhiên. Khi đó tồn tại duy nhất các số tự nhiên c, r với 0 ¤ c b; 0 ¤ r k , sao cho b kc r. Nếu b chia hết cho c thì r 0.
11 Chứng minh. Nếu b k thì c 0; 0 ¤ r b k . Nếu b ¥ k thì theo tiên đề Archimedus tồn tại số c sao cho kc ¤ b ¤ pc 1q k. Đặt r b kc. Khi đó 0 ¤ r b kc k và b kc r. Giả sử tồn tại cặp pc1 , r1 q cũng thỏa b kc1 r1 với 0 ¤ c1 b; 0 ¤ r1 k . Ta sẽ chứng minh rằng c1 c; r1 r. Thật vậy, nếu 0 ¤ r r1 thì r r1 k pc1 cq suy ra r r1 chia hết cho k mà 0 ¤ r, r1 k nên r r1 0. Suy ra c1 c; r1 r. Vậy cặp c, r là duy nhất thỏa mãn biểu thức b kc r Định lý 1.1.29. Cho hai số tự nhiên b và k . Khi đó tồn tại duy nhất biểu diễn của b dưới dạng đa thức của k có dạng: b bn k n bn1 k n1 ... b1 k 1 b0 k 0 , trong đó bj là số nguyên, 0 ¤ bj ¤ k 1, j 0, 1, 2, . . . , n và hệ số đầu tiên bn 0. Chứng minh. Từ Định lý 1.1.28 đem chia b cho k ta được duy nhất cặp pc0; b0q thỏa mãn b kc0 b0 , 0 ¤ b0 ¤ k 1; 0 ¤ c0 b. Nếu b k thì c0 0 suy ra b là đa thức bậc 0. Nếu b ¡ k thì c0 ¡ 0, ta tiếp tục chia c0 cho k để được duy nhất cặp pc1; b1q sao cho 0 ¤ b1 ¤ k 1; 0 ¤ c1 c0 b thỏa mãn c0 kc1 b1 thì b k pkc1 b1 q b0 hay b c1 k 2 b1 k b0 . Nếu c0 k thì c1 ¡ 0 và b là đa thức bậc nhất với k . Nếu c0 ¡ k thì c1 ¡ 0, ta tiếp tục chia c1 cho k để được duy nhất cặp pc2 ; b2 q sao cho 0 ¤ b2 ¤ k 1; 0 ¤ c2 c1 c0 b thỏa mãn c1 kc2 b2 thì b k 2 pkc2 b2 q b1 k b0 c1 k 3 b2 k 2 b1 k b0 . Tiếp tục quá trình đó, ta sẽ thu được dãy ci thỏa mãn: 0 ¤ cn cn 1 . . . c1 c0 ¤ b Sau n 1 bước ta có: b bn k n bn1 k n1 ... b1 k 1 b0 k 0 thỏa mãn điều kiện 0 ¤ bj ¤ k 1, j 0, 1, 2, . . . , n, bn 0.
12 Số k nói trong định lý được gọi là cơ số của biểu diễn. Các hệ số bj được gọi là các chữ số. Nếu số nguyên b biểu diễn trong cơ số k có n chữ số thì từ chứng minh trên ta có: k n b k n 1 . Như vậy, số chữ số của b được tính theo công thức: n rlogk bs 1 log b 1. log k Trong đó, ký hiệu log dùng để chỉ logarit cơ số e, rq s là phần nguyên của số q (số nguyên lớn nhất không vượt quá q ). Trong cơ số tùy ý ta có n Oplog bq. Để phân biệt các biểu diễn của số nguyên trong những hệ cơ số khác nhau ta thường dùng cách viết bn bn1 . . . b1 b0 với chỉ số dưới là cơ số k để viết số b bn k n bn1 k n1 . . . b1 k 1 b0 k 0 . Ví dụ 1.1.30. Chuyển biểu diễn của số 1994 từ hệ đếm cơ số 10 sang hệ đếm cơ số 2. Thực hiện phép chia:
13 Vậy 1994 1 210 1 29 1 28 1 27 1 26 0 25 0 24 1 23 0 22 1 21 0 20 . Nên 1994 111110010102 . Ví dụ 1.1.31. Chuyển biểu diễn của số 1994 từ hệ đếm cơ số 10 sang hệ đếm cơ số 3. Thực hiện phép chia: Vậy 1994 2 36 2 35 0 34 1 33 2 32 1 31 2 30 . Nên 1994 22012123 . Ví dụ 1.1.32. Chuyển biểu diễn của số 1994 từ hệ đếm cơ số 10 sang hệ đếm cơ số 5. Thực hiện phép chia: Vậy 1994 3 54 0 53 4 52 3 51 4 50 . Nên 1994 304345 .
14 1.2 Mảng diatomic của Stern Năm 1858, M.A. Stern đã xây dựng mảng diatomic và nghiên cứu một số tính chất toán học của nó (trong bài báo "Ueber eine zahlenthe- oretische Funktion", Journal f¨ ur die reine und angewandte Mathematik, 55:193–220). Cũng tương tự như tam giác Pascal, mảng diatomic cũng được bắt đầu bởi hai phần tử là hai số nguyên dương a, b (ta gọi là hai đối số). Dòng tiếp theo là: a, a b, b. Các dòng tiếp theo được xác định từ dòng đứng trên nó với qui tắc: liệt kê các số của dòng trên, sau đó xen giữa hai số của dòng mới ta điền thêm vào một số bằng tổng hai số đó. Như vậy, nếu dòng phía trên có k số thì dòng mới xác định có 2 pk 1q 1 2k 1 số mà vị trí “lẻ”: 1, 3, 5, . . . , 2k 3, 2k 1 đều là các số của dòng phía trên, còn các vị trí “chẵn” là các số được tạo thành bằng tổng của 2 số liền kề. Với qui tắc đó ta có bảng sau:
15
16 Từ qui tắc xây dựng mảng diatomic và Bảng 1.1 đã xác định ở trên ta có ngay một số tính chất sau: Tính chất 1.2.1. Số pa bq luôn là phần tử nằm chính giữa các dòng. Tính chất 1.2.2. Các đối số a và b luôn đứng ở đầu và ở cuối mỗi dòng. Tính chất 1.2.3. Nếu a b thì các dòng là đối xứng qua tâm. Tính chất 1.2.4. Nếu một dòng có k phần tử thì dòng tiếp theo sẽ có 2k 1 phần tử. Tính chất 1.2.5. Dòng thứ 2 có ba phần tử: a, a b, b. Dòng thứ n có 2n1 1pq phần tử. Chúng ta dễ dàng chứng minh được khẳng định trên bằng quy nạp. Thật vậy với n 2, dòng thứ 2 có 221 1 3 phần tử, công thức (*) đúng. Giả sử công thức (*) đúng với mọi n k ¥ 2, tức là ở dòng thứ k ta có 2k1 1 phần tử. Chúng ta sẽ chỉ ra rằng công thức (*) đúng với n k 1. Theo cách xây dựng ở trên chúng ta có số phần tử ở dòng thứ k có số phần tử là 2k1 1 nên ở dòng k 1 có số phần tử là 2p2k1 1q 1, dễ thấy 2p2k1 1q 1 2k 1. Điều đó cho thấy công thức (*) được chứng minh. Tính chất 1.2.6. Ký hiệu Sp pa, bq là tổng các phần tử nằm trên dòng thứ p khi đó ta sẽ có: 3p1 1 Sp pa, bq pa bq . (1.4) 2 Chứng minh. Với p 1, dòng thứ nhất có 2 phần tử a, b và 311 1 S1 pa, bq pa bq a b, 2 mệnh đề đúng. Với p 2, ta có 321 1 S2 pa, bq pa bq 2 pa bq , 2
17 mệnh đề vẫn đúng. Giả sử mệnh đề đúng với mọi p 1 ¥ 1, tức là chúng ta có 3p2 1 Sp1 pa; bq pa bq . 2 Chúng ta sẽ chỉ ra mệnh đề đúng với p, tức là 3p1 1 Sp pa; bq pa bq . 2 Thật vậy, do cách tạo dòng thứ p từ dòng thứ p 1 ta có: dòng thứ p gồm các phần tử của dòng thứ p 1 và giữa hai phần tử của dòng vừa viết lại được thêm vào một phần tử bằng tồng của 2 phần tử đó, nên tất cả các phần tử của dòng p 1 được tính hai lần trừ phần tử đứng ở vị trí đầu dòng và cuối dòng. Do vậy, Sp pa, bq Sp1 pa, bq 2Sp1 pa, bq a b 3Sp1pa, bq pa bq 3p2 1 3. 2 pa bq pa bq 3p1 1 2 pa bq . Mệnh đề được chứng minh. Tính chất 1.2.7. Với 2 số nguyên dương a, b ta luôn có Sp pa, bq Sp pb, aq . Tính chất 1.2.8. Cho a, a1 , b, b1 là các số nguyên dương bất kỳ. Khi đó ta luôn có Sp pa a1 , b b1 q Sp pa, bq Sp pa1 , b1 q . (1.5) Chứng minh. Ta có 3p1 Sp pa a1 , b bq 1 pa a1 b1 q 1 b 2 p1 3p1 1 1 2 pa bq 3 1 2 pa b1 q Sppa, bq Sppa1 b1 q.
18 Tính chất 1.2.9. Nếu a và b là hai số nguyên tố cùng nhau thì trên cùng một dòng, hai phần tử bất kỳ liền nhau không có ước chung thực sự. Hơn nữa, trong bộ ba: m, n, s pn m sq liền nhau trong một dòng ta luôn có pm, sq 1. Chứng minh. Giả sử pa, bq 1. Trên dòng 2 ta có pa, a bq 1, pa b, bq 1 (hiển nhiên), mệnh đề đúng với dòng p 2. Giả sử mệnh đề đúng với dòng p 1, nghĩa là trên dòng thứ p 1, hai phần tử liền kề nhau bất kỳ là nguyên tố cùng nhau. Xét hai phần tử liền kề nhau bất kỳ trên dòng thứ p là m và n. Khi đó hoặc m, hoặc n là ở vị trí có số thứ tự chẵn trên dòng p và nó bằng tổng của hai phần tử cạnh nó. + Nếu m ở vị trí hàng chẵn thì ta có t, m, n là ba phần tử liền nhau trên dòng p và m t n. Theo giả thiết qui nạp, pt, nq 1 vì là hai phần tử sát nhau trên dòng p 1 nên pt n, nq pm, nq 1. + Tương tự nếu n ở vị trí chẵn thì m, n, s là ba phần tử liền nhau trên dòng p và n m s, vì pm, sq 1 nên pm, m sq pm, nq 1. Cũng theo chứng minh trên ta thấy nếu m, n, s là ba phần tử liền nhau trên một dòng. Nếu n là vị trí chẵn hiển nhiên pm, sq 1. Nếu n là vị trí lẻ, khi đó m và s là vị trí chẵn và ta có m n u với pn, uq 1, s n v với pn, vq 1. Vì pm, nq 1 nên pm, n vq 1. Điều phải chứng minh. Tính chất 1.2.10. Thứ tự hai phần tử liền nhau m, s trên một hàng không thể lặp lại trên dòng đó và không xuất hiện trên mọi dòng khác dưới nó. Tính chất 1.2.11. Hai bộ ba pm, s, nq , pn, s, mq ps m nq không thể xuất hiện trên nửa đầu hoặc nửa sau của một dòng. 1.3 Dãy diatomic của Stern Xét mảng diatomic của Stern (Bảng 1.1) khi a b 1, ta có bảng sau: