..
ĐẠ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
1.1 Các kiến thức chuẩn bị . . . . . . . . . . . .
1.1.1 Một số định nghĩa . . . . . . . . . . .
1.1.2 Dãy Fibonacci . . . . . . . . . . . . .
1.1.3 Dãy Jacobsthal . . . . . . . . . . . .
1.1.4 Hệ cơ số . . . . . . . . . . . . . . . .
1.2 Mảng diatomic của Stern . . . . . . . . . . .
1.3 Dãy diatomic của Stern . . . . . . . . . . . .
Stern
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Chương 2. Các tính chất của dãy diatomic và mảng diatomic
của Stern
2.1 Biểu diễn siêu nhị phân của một số tự nhiên . . . . . . . .
2.2 So sánh với tam giác Pascal . . . . . . . . . . . . . . . . . .
2.3 Mô tả tập số hữu tỉ qua dãy Stern . . . . . . . . . . . . . .
Chương 3. Ứng dụng của dãy diatomic và mảng
Stern
3.1 Số hợp lý Stern trung bình . . . . . . . . . .
3.2 Cặp Stern, mod d . . . . . . . . . . . . . . .
3.3 Hàm Minkowski . . . . . . . . . . . . . . . .
5
5
5
7
9
10
14
18
23
23
25
32
diatomic của
38
. . . . . . . . 38
. . . . . . . . 40
. . . . . . . . 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ür 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
1.1.1
Các kiến thức chuẩn bị
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.
Vậy p4, 7q 1.
r4, 7s ÞÑ r4, 3s ÞÑ r1, 3s ÞÑ r1, 2s ÞÑ r1, 1s .
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
'
'
%F
n 1 Fn
Fn 1
pn ¥ 1q.
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
? 1
Fn
2n 5
?
?
1
1 5
5
và φ
.
trong đó φ
5
1
2
n
5
φn φ
φφ
n
(1.1)
2
Một vài tính chất của dãy Fibonaci:
q 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 .
Tính chất 1.1.11. Với số nguyên dương n bất kỳ ta có:pFn , Fn
1
Mệnh đề 1.1.13. Với hai số nguyên dương m, n bất kỳ ta có đẳng thức:
Fm1.Fn 1 Fm.Fn.
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
Fm
minh:
Fm
(1.2)
n
k 1
Fm1.Fk
1
Fm .Fk , ta chứng
1
Fm .Fk
Fm .Fk 1 .
2
Thật vậy, ta có:
Fm
k 1
Fm k 1 Fm k
Fm1.Fk Fm.Fk1
Fm1. pFk Fk 1q
Fm1.Fk 2 Fm.Fk
Fm1 .Fk
Fm . pFk1
Fk q
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
tố.
¥ 5 và Fn là số nguyên tố thì n cũng là số nguyên
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
chia hết cho 5.
¥ 1 ta có: F5n 5Fnqn, qn không
Tính chất 1.1.19. Với số nguyên n ¥ 1 ta có:
Fn pFn1 Fn 1q .
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 .
F2n
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 .
Tính chất 1.1.23. Với số nguyên n ¥ 1 ta có:
Fn Fn 1 Fn1 Fn 2 p1qn1 .
F2n
1.1.3
1
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
'
'
%J
n 1 Jn
2Jn1 , n 1, 2, 3, . . .
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
.
(1.3)
Jn
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
là phải chứng minh:
2n 1 p1qn 1
.
Jn 1
3
Ta có,
Jn
1
Jn
2Jn1
1, tức
2n p1qn
2n1 p1qn1
2.
3
3
n
n
n
2.2 p1q
2.p1q
3
n 1
2
p1qn
3
n 1
2
p1q p1qn
3
n 1
2
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
n
2.p1q 3 p1q
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
trong đó bj là số nguyên, 0
tiên bn 0.
...
b1 k 1
b0 k 0 ,
¤ bj ¤ k 1, j 0, 1, 2, . . . , n và hệ số đầu
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
Sau n
cn 1 . . . c1 c0 ¤ b
1 bước ta có:
b bn k n
thỏa mãn điều kiện 0 ¤ bj
bn1 k n1
...
b1 k 1
b0 k 0
¤ 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:
log b
1.
n rlogk bs 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
0 24
1 29
Nên 1994 111110010102 .
1 23
1 28
0 22
1 27
1 21
1 26
0 20 .
0 25
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
Nên 1994 22012123 .
0 34
1 33
2 32
1 31
2 30 .
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
Nên 1994 304345 .
0 53
4 52
3 51
4 50 .
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 zahlentheoretische Funktion", Journal für 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
2n1 1pq phần tử.
b, b. Dòng thứ n có
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ó:
Sp pa, bq
3p1 1
pa
2
bq .
(1.4)
Chứng minh. Với p 1, dòng thứ nhất có 2 phần tử a, b và
S1 pa, bq
311 1
pa
2
bq a
b,
mệnh đề đúng. Với p 2, ta có
S2 pa, bq
321 1
pa
2
bq 2 pa
bq ,
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
pa bq .
Sp1 pa; bq
2
Chúng ta sẽ chỉ ra mệnh đề đúng với p, tức là
Sp pa; bq
3p1 1
pa
2
bq .
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
3p1 1
pa
2
bq
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ó
Sp pa
a1 , b
3p1
1
bq
1
2
p1
pa
a1
2 pa bq
Sppa, bq Sppa1
3
1
b
b1 q
3p1 1 1
pa
2
b1 q.
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
xuất hiện trên nửa đầu hoặc nửa sau của một dòng.
1.3
nq không thể
Dãy diatomic của Stern
Xét mảng diatomic của Stern (Bảng 1.1) khi a
sau:
b 1, ta có bảng
- Xem thêm -