Luận văn Thạc sĩ Toán học: Định lý nhị thức số

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

Thêm vào BST

Báo xấu

20
lượt xem 4
download

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

Luận văn trình bày các nội dung: Định lý nhị thức và định lý nhị thức dạng số hóa dựa theo hàm tổng kí tự; định lý nhị thức số tổng quát cho cơ số b ≥ 2 bất kỳ bằng cách xây dựng ma trận một tham số của ma trận Sierpinski tổng quát. Ngoài ra, chúng ta trình bày một công thức mới cho hệ số của đa thức Prouhet–Thue–Morse.

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: Định lý nhị thức số

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGUYỄN THỊ QUỲNH HOA ĐỊNH LÝ NHỊ THỨC SỐ 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 PGS. TS. NÔNG QUỐC CHINH Thái Nguyên, 04/2019
i Mục lục Mở đầu 1 Chương 1. Định lý nhị thức số 3 1.1 Định lý nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Biểu diễn nhị phân của số nguyên . . . . . . . . . . . . . . . . . . . 6 1.3 Ma trận Sierpinski . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Định lý nhị thức số . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chương 2. Định lý nhị thức số tổng quát 19 2.1 Ma trận Sierpinski tổng quát . . . . . . . . . . . . . . . . . . . . . 19 2.2 Định lý nhị thức số tổng quát . . . . . . . . . . . . . . . . . . . . . 22 2.3 Các đa thức Prouhet–Thue–Morse . . . . . . . . . . . . . . . . . . 26 Chương 3. Ứng dụng của định lý nhị thức số 33 3.1 Phép biến đổi nhị thức của các dãy Dold . . . . . . . . . . . . . . 33 3.2 Ứng dụng cho tổng nhị thức . . . . . . . . . . . . . . . . . . . . . . 39 Kết luận 47 Tài liệu tham khảo 48
1 Mở đầu Ta đã biết hệ số nhị thức xuất hiện trong định lý nhị thức khi thực hiện lũy thừa bậc n của một tổng (nhị thức Newton) n X n k n−k (x + y)n = x y , n ∈ N. k k=0 n Các hệ số nhị thức k được xác định rất cụ thể ở vị trí thứ k, hàng thứ n của tam giác Pascal. Lấy modulo 2 của các số hạng của tam giác Pascal (hay các hệ số nhị thức) ta thu được tam giác Sierpinski. Năm 2014, H.D. Nguyen [4] đã trình bày một định lý tương tự định lý nhị thức đó là Định lý nhị thức số. Ký hiệu s(m) là tổng tất cả các ký tự trong biểu diễn nhị phân của m. Khi đó Định lý nhị thức số được phát biểu như sau: Với mọi n ∈ N ta có X (x + y)s(m) = xs(k) y s(m−k) . 0≤k≤m (k,m−k) carry-free Một năm sau đó, H.D. Nguyen [5] đã mở rộng kết quả trên dưới dạng định lý nhị thức số tổng quát, mà định lý nhị thức là một trường hợp riêng của định lý này. Luận văn này, chúng tôi chọn đề tài “Định lý nhị thức số” để làm nội dung nghiên cứu. Mục tiêu của luận văn là trình bày lại các kết quả về định lý nhị thức thông qua hai bài báo bằng tiếng Anh của H.D. Nguyen là [4, 5]. Ngoài ra, chúng tôi cũng trình bày một kết quả khác liên quan tới hệ số nhị thức, đó là phép biến đổi nhị thức của một dãy số dựa vào một bài báo của Klaudiusz Wójcik [7]. Ngoài phần Bảng ký hiệu, Mở đầu, Kết luận và Tài liệu tham khảo, bố cục của luận văn được chia làm ba chương.
2 Chương 1. Định lý nhị thức số. Chương này trình bày định lý nhị thức và định lý nhị thức dạng số hóa dựa theo hàm tổng kí tự. Chương 2. Định lý nhị thức số tổng quát. Trong chương này ta trình bày định lý nhị thức số tổng quát cho cơ số b ≥ 2 bất kỳ bằng cách xây dựng ma trận một tham số của ma trận Sierpinski tổng quát. Ngoài ra, chúng ta trình bày một công thức mới cho hệ số của đa thức Prouhet–Thue–Morse. Chương 3. Ứng dụng của định lý nhị thức số. Trong chương này ta trình bày biến đổi nhị thức T (a) của dãy Dold. Luận văn này đượ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 và chỉ bảo tận tình của PGS. TS Nông Quốc Chinh. Tác giả xin được bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm, động viên, chỉ bảo hướng dẫn tận tình của thầy Nông Quốc Chinh. Tác giả xin chân thành cảm ơn tới các thầy cô giáo phòng Đào tạo, các thầy cô giáo khoa Toán Tin, cũng như các thầy cô giáo đã tận tâm giảng dạy, hướng dẫn, giúp đỡ tác giả trong quá trình học tập và hoàn thành luận văn này. Cuối cùng tác giả cũng xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã luôn quan tâm, động viên và tạo mọi điều kiện thuận lợi trong suốt quá trình học tập để tác giác hoàn thành hóa học và hoàn thiện luận văn. Xin chân thành cảm ơn. Thái Nguyên, tháng 4 năm 2019 Người viết luận văn Nguyễn Thị Quỳnh Hoa
3 Chương 1 Định lý nhị thức số Nội dung của chương này là trình bày định lý nhị thức và định lý nhị thức dạng số hóa dựa theo hàm tổng kí tự. Bên cạnh cách chứng minh định lý nhị thức số dạng số hóa tương tự như định lý nhị thức, ta còn có thể chứng minh nó dựa theo công thức ma trận suy rộng một tham số của tam giác Sierpinski. 1.1 Định lý nhị thức Định nghĩa 1.1.1 ([6]). Cho n, m là số nguyên không âm. Hệ số nhị thức được định nghĩa bởi n!  , n ≥ m; n  = m!(n − m)! m 0, n < m. 8 8! 7 n Ví dụ, 3 = 3!5! = 56 và 9 = 0. Hệ số nhị thức m ký hiệu số tổ hợp chập m của n phần tử phân biệt. Nguồn gốc của tên gọi hệ số nhị thức xuất phát từ định lý quan trọng sau. Định lý 1.1.2 (Định lý nhị thức, [6]). Hệ số của xn−k y k trong khai triển của (x + y)n là nk . Nói cách khác, ta có công thức n n n n n n (x+y)n = xn + xn−1 y + xn−2 y 2 +· · ·+ xy n−1 + y . (1.1) 0 1 2 n−1 n Chứng minh. Ta chứng minh kết quả bằng phương pháp qui nạp theo n. Với n = 0, 1 công thức hiển nhiên đúng. Giả sử công thức đúng với n. Ta chỉ ra nó đúng với n + 1. Thật vậy, theo giả thiết quy nạp ta có: n n hX i (x + y)n+1 = (x + y)n (x + y) = xr y n−r (x + y) r r=0
4 n n X n X n = xr+1 y n−r + xr y n−r+1 r r r=0 r=0 hn i hn i n n+1 n n n = y + + xy + + x2 y n−1 + · · · 0 0 1 1 2 h n i n n n+1 + + xn y + x n−1 n n n+1 X n+1 = xr y n+1−r . r r=0 n+1 n+1 Từ đó suy ra (x + y)n+1 = xr y n+1−r . Vậy ta suy ra công thức đúng với P r r=0 n + 1. Tóm lại, công thức đúng với mọi số nguyên không âm n. Ta có thể áp dụng định lý nhị thức theo nhiều cách khác nhau để thu được các công thức khác nhau liên quan đến hệ số nhị thức. Ví dụ, thay x = y = 1, thì ta được n n n n n n 2 = + + + ··· + . 0 1 2 n−1 n Hệ quả 1.1.3. Cho x là số thực bất kỳ. Khi đó, ta có n X n r (1 + x)n = x . r r=0 Hệ số nhị thức thỏa mãn nhiều công thức quan trọng. Định lý 1.1.4 ([6]). Hệ số nhị thức thỏa mãn các công thức sau: n n = ; (1.2) k n−k n−1 n−1 n + = ; (đẳng thức Pascal) (1.3) k−1 k k n n n n n + + + ··· + + = 2n . (1.4) 0 1 2 n−1 n Chứng minh. Theo định nghĩa ta có: n n! n! n = = = . k k!(n − k!) (n − k)!(n − (n − k))! n−k Xét đẳng thức n! (n − 1)! (n − 1)! = + . k!(n − k)! (k − 1)!(n − k)! k!(n − k − 1)!
5 Chia cả hai vế của đẳng thức với (n − 1)! rồi nhân cả hai vế của đẳng thức với (k − 1)!(n − k − 1)!, đẳng thức trở thành n 1 1 = + . k(n − k) n−k k Đẳng thức trên đúng nên (1.3) đúng. Thay x = y = 1 vào công thức hệ số nhị thức ta thu được (1.4). n Định lý 1.1.5 ([6]). Hệ số nhị thức m là số nguyên với mọi n ≥ 0. Chứng minh. Ta chứng minh bằng phương pháp quy nạp. Vì m0 = 0 là một số nguyên, định lý đúng với n = 0. Giả sử định lý đúng vói mọi số nguyên không âm < k. Khi đó, k−1 k−1 là số nguyên. Nên tổng của chúng k−1 k−1 r−1 và r r−1 + r là số nguyên theo đẳng thức Pascal. Do đó, theo nguyên lý quy nạp, tất cả các hệ số nhị thức đều là số nguyên. Hệ quả 1.1.6 ([6]). Tích của r số nguyên liêp tiếp chia hết cho r!. Chứng minh. Ta chỉ cần chứng minh hệ quả với số nguyên dương. Gọi n là số nhỏ nhất trong r số. Vì n(n + 1) · · · (n + r − 1) (n + r − 1)! n+r−1 = = . r! r!(n − 1)! r n(n + 1) · · · (n + r − 1) Theo Định lý 1.1.5, là số nguyên nên n(n + 1) · · · (n + r − 1) r! chia hết cho r!. Bổ đề 1.1.7 (Gould, [3]). n X x+k y+n−k x+y+n+1 = . (1.5) k n−k n k=0 Chứng minh. Gould [3] tìm ra (1.5) làm một trường hợp riêng của công thức tích chập Vandermonde. Ta sẽ chứng minh (1.5) một cách trực tiếp bằng công cụ tổ hợp. Ký hiệu A là tập chứa x phần tử phân biệt, B là tập chứa y phần tử phân biệt và C = {0, 1, . . . , n} là tập chứa n + 1 phần tử phân biệt, trong đó n là một số nguyên dương. Với số nguyên không âm k bất kỳ, định nghĩa Ak = A ∪ {0, . . . , k − 1} và Bk = B ∪ {k + 1, . . . , n}. Cho tập con S bất kỳ gồm n phần tử của A ∪ B ∪ C, tồn tại duy nhất số nguyên kS thuộc C − S, được gọi là chỉ số của S đối với A và B , sao cho |S ∩ AkS | và |S ∩ BkS | = n − kS . Để thấy
6 điều này, định nghĩa SA = A ∩ S, SB = B ∩ S, và T = C − S. Ta bắt đầu bằng việc xóa |SA | phần tử liên tiếp khỏi T theo thứ tự tăng dần và bắt đầu từ phần tử nhỏ nhất, để thu được tập T 0 . Sau đó, ta xóa |SB | phần tử liên tiếp khỏi T 0 , theo thứ tự giảm dần bằng đầu từ phần tử lớn nhất của nó để thu được tập con T 00 , và bây giờ phải chứa một phần tử đơn ký hiệu bởi kS . Bây giờ rõ ràng |S ∩ AkS | = kS và |S ∩ BkS | = n − kS . Để chứng minh (1.5), ta đếm các tập con n phần tử S của A ∪ B ∪ C theo hai cách. Một mặt, vì |A ∪ B ∪ C| = x + y + n + 1, số tập con S là x+y+n+1 n . Mặt khác, ta chia tất cả các tập n phần tử như này thành hai phần bằng nhau theo giá trị chỉ số của tập các tập con đó. Vì |S ∩ Ak | = k và |S ∩ Bk | = n − k , suy ra y+n−k số tập con S có cùng chỉ số k là x+kk n−k và tổng số tập con S là n X x+k y+n−k . k n−k k=0 Cuối cùng, cân bằng hai đáp án ta thu được (1.5). Bổ đề 1.1.8 ([5]). Cho p và q là hai số nguyên dương với p ≤ q. Khi đó ta có p X x+p−v−1 y+v−q−1 x+y+p−q−1 = . (1.6) p−v v−q p−q v=q Chứng minh. Đặt k = v − q và n = p − q. Khi đó (1.6) có thể được viết lại thành p−q X x+p−q−w−1 y+w−1 x + +y + p − q − 1 = , p−q−w w p−q w=0 nên đúng theo Bổ đề 1.1.7. 1.2 Biểu diễn nhị phân của số nguyên Trong hệ thập phân, ta biểu diễn số sử dụng các kí tự {0, 1, . . . , 9} với cơ số 10, tức là số được biểu diễn thành tổng của các lũy thừa của 10. Ví dụ, 23810 = 2 · 102 + 3 · 101 + 8 · 100 . Tổng quát, biểu diễn thập phân của số X có dạng X X= di · 10i , (di ∈ {0, 1, 2, . . . , 9}). i
7 Máy tính không biểu diễn số bằng hệ thập phân, thay vào đó, máy tính biểu diễn số bằng hệ nhị phân. Tất cả các phép toán, tính chất của phép cộng, phép trừ, phép nhân và phép chia đều đúng với hệ nhị phân. Trong hệ nhị phân, ta chỉ có hai kí tự 0 và 1. Do đó, ta nói các số trong hệ nhị phân được biểu diễn với cơ số 2, tức là một số bất kỳ được biểu diễn thành tổng của các lũy thừa của 2. Ví dụ, 110102 = 1 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 0 · 20 . Tổng quát, biểu diễn nhị phân của số X có dạng X X= di · 2i , (di ∈ {0, 1}). i Việc chuyển một số nhị phân sang số thập phân là đơn giản. Ta chỉ cần tính tất cả các lũy thừa của 2 rồi cộng các số này lại. Ví dụ, 110102 = 16 + 8 + 2 = 26. Để chuyển một số từ hệ thập phân sang hệ nhị phân thì phức tạp hơn. Ở đây ta chỉ xét chuyển số nguyên sang dạng nhị phân. Nhắc lại rằng, một số nguyên biểu diễn bởi bm−1 bm−2 . . . b2 b1 b0 , bi = 0 hoặc 1 có giá trị bm−1 · 2m−1 + bm−2 · 2m−2 + · · · + b1 · 21 + b0 . Giả sử ta muốn chuyển số nguyên thập phân N sang dạng nhị phân. Nếu ta chia N cho 2 trong dạng thập phân, và thu được thương N1 và phần dư R0 , ta có thể viết N = 2 · N1 + R0 , R0 = 0 hoặc 1. Tiếp theo, ta chia N1 cho 2. Giả sử thương mới là N2 và phần dư mới là R1 . Khi đó N1 = 2 · N2 + R1 , R1 = 0 hoặc 1 nên N = 2(2N2 + R1 ) + R0 = N2 · 22 + R1 · 21 + R0 . Nếu tiếp theo ta có N2 = 2N3 + R3
8 thì N = N3 · 23 + R2 · 22 + R1 · 21 + R0 . Bởi vì N > N1 > N2 > . . . , tiếp tiếp dãy này sau cùng sẽ sinh ra thương Nm−1 = 1 (ngoại trừ với số thập phân 0 và 1, mà có biểu diễn nhị phân tương ứng là 0 và 1) và phần dư Rm−2 là 0 hoặc 1. Khi đó, ta có N = 1 · 2m−1 + Rm−2 · 2m−2 + · · · + R2 · 22 + R1 · 21 + R0 chính là biểu diễn nhị phân của N. Do đó, ta chuyển từ hệ 10 sang hệ 2 bằng cách thực hiện liên tiếp phép chia cho 2. Phần dư và thương cuối cùng 1 theo thứ tự là biểu diễn nhị phân của N. Ví dụ 1.2.1. Tìm biểu diễn nhị phân của 241. Áp dụng thuật toán bên trên ta có Thương Phần dư Giải thích 241 120 1 241 = 120 · 2 + 1 60 0 120 = 60 · 2 + 0 30 0 60 = 30 · 2 + 0 15 0 30 = 15 · 2 + 0 7 1 15 = 7 · 2 + 1 3 1 7=3·2+1 1 1 3=1·2+1 0 1 1=0·2+1 Do đó, 24110 = 111100012 . Chúng ta liệt kê biểu diễn nhị phân của số nguyên không âm từ 0 đến 11: 0 = 02 6 = 1102 1 = 12 7 = 1112 2 = 102 8 = 10002 3 = 112 9 = 10012 4 = 1002 10 = 10102 5 = 1012 11 = 110002 .
9 Định nghĩa 1.2.2 ([1]). Cho hai số nguyên không âm i và j , số i được gọi là (nhị phân)-tự do của j nếu biểu diễn nhị phân của i có các kí tự 0 ở vị trí mà j có kí tự 1, hay tương đương khi ta thực hiện phép cộng i và j theo cơ số 2 thì không có “nhớ”. Khi đó ta còn gọi cặp số nguyên không âm (i, j) là carry-free. Ví dụ 1.2.3. Cho i = 101012 , j = 1010102 thì (i, j) là carry-free. Cặp (8, 2) là carry-free vì 8 = 10002 , 2 = 102 nên khi thực hiện 8 + 2 là carry-free. Ví dụ 1.2.4. Với 0 ≤ i < j ≤ 7, các cặp số sau đây là các cặp số carry-free: (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 2), (1, 4), (1, 6), (2, 4), (2, 5), (3, 4). Với 0 ≤ i < j ≤ 7, các cặp số sau đây là các cặp số có nhớ: (1, 3), (1, 5), (1, 7), (2, 3), (2, 6), (2, 7), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 6), (5, 6), (5, 7), (6, 7). Bổ đề 1.2.5 ([1]). Cặp số nguyên không âm (i, j) là carry-free khi và chỉ khi i+j j là số lẻ. Định nghĩa 1.2.6 ([4]). Hàm tổng các các kí tự của số nguyên k = (bm . . . b2 b1 b0 )2 , ký hiệu s(k), xác định bởi s(k) = bm + · · · + b2 + b1 + b0 . Ví dụ 1.2.7. Ta có s(0) = s(02 ) = 0 s(1) = s(12 ) = 1 s(2) = s(102 ) = 1 + 0 = 1 s(3) = s(112 ) = 1 + 1 = 2 s(4) = s(1002 ) = 1 + 0 + 0 = 1 s(5) = s(1012 ) = 1 + 0 + 1 = 2 s(6) = s(1102 ) = 1 + 1 + 0 = 2 s(7) = s(1112 ) = 1 + 1 + 1 = 3.
10 Định nghĩa 1.2.8 ([4]). Hàm nhớ c(n, k) của hai số nguyên n và k được xác định bằng số lần thực hiện nhớ khi thực hiện phép cộng k và n − k trong biểu diễn nhị phân. Ta có s(k) + s(n − k) − s(n) = c(n, k). Suy ra cặp số (k, n − k) là carry-free khi và chỉ khi s(k) + s(n − k) = s(n). 1.3 Ma trận Sierpinski Tam giác Pascal là một bảng hình tam giác gồm các hệ số nhị thức. Các hàng của tam giác Pascal được đánh số bắt đầu với n = 0 tại hàng đầu tiên (hàng thứ 0). Các số ở mỗi hàng được đánh số từ trái qua phải, bắt đầu với k = 0. Tức là, số hạng ở hàng thứ n, cột thứ k là nk . Một số hàng đầu tiên của tam giác Pascal được minh họa trong hình bên dưới. Lấy modulo 2 các số hạng của tam giác Pascal (hay các hệ số nhị thức) ta được tam giác Sierpinski. Dồn các số hạng của tam giác Sierpinski sang bên trái và bổ sung số 0 vào các vị trí còn thiếu, ta thu được ma trận Sierpinski:   1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0     1 0 1 0 0 0 0 0   1 1 1 1 0 0 0 0   1 0 0 0 1 0 0 0   1 1 0 0 1 1 0 0     1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1
11 Định nghĩa 1.3.1. Nếu A là ma trận cỡ m × n và B là ma trận cỡ p × q thì tích Kronecker A ⊗ B là ma trận cỡ mp × nq xác định bởi   a11 B ··· a1n B  . ... .. A ⊗ B =  .. ,  . am1 B · · · amn B cụ thể hơn, ta có   a11 b11 a11 b12 ··· a11 b1q ··· a1n b11 a1n b12 ··· a1n b1q a b  11 21 a11 b22 ··· a11 b2q ··· a1n b21 a1n b22 ··· a1n b2q    .. .. ... .. .. .. ... ..   . . . . . .     a11 bp1 a11 bp2  ··· a11 bpq ··· a1n bp1 a1n bp2 ··· a1n bpq    . .. .. ... .. .. ..  A ⊗ B =  .. . . . . .    am1 b11 am1 b12  ··· am1 b1q · · · amn b11 amn b12 · · · amn b1q   a b  m1 21 am1 b22 ··· am1 b2q · · · amn b21 amn b22 · · · amn b2q    .. .. ... .. .. .. ... ..   . . . . . .  am1 bp1 am1 bp2 · · · am1 bpq · · · amn bp1 amn bp2 · · · amn bpq Ví dụ 1.3.2. Cho hai ma trận " # " # 1 2 0 5 A= và B = , 3 4 6 7 ta có  " # " #   0 5 0 50 5 0 10 1 2   6 7 6 7   6 7 12 14  A⊗B = " # " # =     0 5   0 15 0 20  0 5 3 4 6 7 6 7 18 21 24 28 1.4 Định lý nhị thức số H. D. Nguyen [4] đã giới thiệu dạng số hóa của định lý nhị thức dựa vào công thức ma trận suy rộng một tham số của tam giác Sierpinski được giới thiệu bởi Callan [1], trong đó số mũ trong (1.1) được thay bằng hàm tổng kí tự. Để minh họa điều này, xét định lý nhị thức với n = 2: (x + y)2 = x2 y 0 + x1 y 1 + x1 y 1 + x0 y 2 .
12 Dễ kiểm tra được đẳng thức trên tương đương với (x + y)s(3) = xs(3) y s(0) + xs(2) y s(1) + xs(1) y s(2) + xs(0) y s(3) . Tổng quát hơn, ta có Định lý 1.4.1 (Định lý nhị thức số, [4]). Với mọi m ∈ N ta có X (x + y)s(m) = xs(k) y s(m−k) . (1.7) 0≤k≤m (k,m−k) carry-free Chứng minh. Ta sẽ chứng minh Định lý 1.4.1 và chỉ ra rằng nó tương đương với định lý nhị thức khi m = 2n − 1. Ta chứng minh định lý bằng quy nạp. Xét khai triển nhị thức dạng số hóa như sau: cho hai tập kí tự S0 = {x0 , y0 } và S1 = {x1 , y1 }, ta có thể biểu diễn tất cả cách xây dựng số hai kí tự z0 z1 , trong đó z0 ∈ S0 và z1 ∈ S1 , bằng khai triển (x0 + y0 )(x1 + y1 ) = x0 x1 + x0 y1 + y0 x1 + y1 y1 , (1.8) mà ta có thể viết lại thành (x0 + y0 )(x1 + y1 ) = (x10 x11 )(y00 y10 ) + (x10 x01 )(y00 y11 ) + (x00 x11 )(y01 y10 ) + (x00 x01 )y01 y11 ). (1.9) Bây giờ, nếu ta giả sử x0 = x1 = x và y0 = y1 = y thì mỗi số hạng ở vế phải của (1.9) có dạng xd00 xd11 y01−d0 y11−d1 = xs(k) y s(3−k) , trong đó k = d0 20 + d1 21 và 3 − k = (1 − d0 )20 + (1 − d1 )21 . Do đó, ta thu được X (x + y)s(3) = xs(3) y s(0) + xs(2) y s(1) + xs(1) y s(2) + xs(0) y s(3) = xs(k) y s(3−k) . 0≤k≤3 (k,3−k) carry-free Hay định lý đúng với m = 3 = 22 − 1 (với n = 2). Để mở rộng chứng minh cho m = 2n − 1, ta xét n tập Sk = {xk , yk }, k = 0, 1, . . . , n − 1. Khai triển n−1 Y X X dn−1 1−d0 1−dn−1 (xk + yk ) = z0 · · · zn−1 = xd00 · · · xn−1 y0 · · · yn−1 (1.10) k=0 zk ∈Sk dk ∈{0,1} ∀k=0,1,...,n−1 ∀k=0,1,...,n−1 biểu diễn tất cả cách xây dựng số n kí tự z = z0 · · · zn−1 với zk ∈ Sk với k = 0, 1, . . . , n − 1. Thay xk = x và yk = y , k = 0, 1, . . . , n − 1 vào (1.10) kéo theo X (x + y)n = xd0 +···+dn−1 y n−(d0 +···+dn−1 ) , (1.11) d0 ,...,dn−1 ∈{0,1}
13 hay tương đương n 2X −1 n n −1) −1−k) (x + y)s(2 = xs(k) y s(2 , (1.12) k=0 ở đó, nếu ta đặt k = d0 20 + · · · dn−1 2n−1 thì s(k) = d0 + · · · + dn−1 và s(2n − 1 − k) = s(2n − 1) − s(k) = n − (d0 + · · · + dn−1 ). Ngoài ra, vì d0 , . . . , dn−1 ∈ {0, 1} nên k biến thiên từ 0 tới 2n − 1. Từ đây kéo theo Định lý 1.1.2. Mặt khác, cho k ∈ [0, n], số hoán vị (d0 , . . . , dn−1 ) chứa k kí tự 1 là nk . Do đó, (1.11) rút gọn thành (1.1). Điều này chứng minh Định lý 1.4.1 là tương đương với định lý nhị thức. Để hoàn thành chứng minh Định lý 1.4.1 với số nguyên không âm m bất kỳ, đầu tiên ta biểu diễn m dưới dạng nhị phân: m = mi0 2i0 + . . . + min−1 2in−1 , trong đó ta chỉ ghi lại các kí tự 1 để mik = 1 với mọi k = 0, . . . , n − 1. Khi đó s(m) = mi0 + · · · + min−1 = n. Như trước đây, ta sử dụng khai triển (1.10) để suy ra (1.11), nhưng lần này ta viết (1.11) thành X (x + y)s(m) = xs(k) y s(m−k) , (1.13) 0≤k≤m (k,m−k) carry-free trong đó ta định nghĩa k = d0 2i0 + · · · + dn−1 2in−1 . (1.14) Khi đó, s(k) = d0 + · · · + dn−1 và vì mik = 1 với mọi k = 0, . . . , n − 1, ta có m − k = (mi0 2i0 + · · · + min−1 2in−1 ) − (d0 2i0 + · · · + mn−1 2in−1 ) = (1 − d0 )(2i0 ) + · · · (1 − dn−1 )2in−1 . Suy ra s(m − k) = (1 − d0 ) + · · · (1 − dn−1 ) = n − (d0 + · · · + dn−1 ). Ngoài ra, rõ ràng 0 ≤ k ≤ m và (k, m − k) là carry-free. Ngược lại, mọi số nguyên không âm k với (k, m−k) là carry-free phải có biểu diễn dạng (1.14) vì nếu ngược lại, tổng k + (m − k) sẽ có nhớ ở kí tự khác không của k trong đó kí tự tương ứng của m ở cùng vị trí bằng không, mâu thuẫn. Do đó, Định lý 1.4.1 đúng với mọi số nguyên không âm m.
14 Ví dụ 1.4.2. Với m = 5, ta có (x + y)s(5) = xs(5) y s(0) + xs(4) y s(1) + 0y s(2) + 0y s(3) + xs(1) y s(4) + xs(0) y s(5) . Theo Ví dụ 1.2.7, ta có s(0) = 0, s(1) = 1, s(2) = 1, s(3) = 2, s(4) = 1, s(5) = 2 nên ta thu được đẳng thức (x + y)2 = x2 y 0 + x1 y 1 + x1 y 1 + x0 y 2 . Đây cũng chính là định lý nhị thức với n = 2. Ta sẽ thấy định lý nhị thức lại được suy ra từ ma trận suy rộng một tham số của tam giác Sierpinski. Mối liên hệ giữa chúng được rút ra từ hàm tổng các kí tự s(k) xác định trong Định nghĩa 1.2.6. Với mục tiêu này, ta bắt đầu với công thức ma trận đã biết của tam giác Sierpinski. Ký hiệu ma trận tam giác Sierpinski là S . Định nghĩa dãy ma trận Sn có cỡ 2n × 2n một cách truy hồi như sau " # 1 0 S1 = (1.15) 1 1 và Sn+1 = S1 ⊗ Sn (1.16) với n > 1. Ở đây, toán tử ⊗ là tích Kronecker của hai ma trận. Ví dụ, S2 và S3 được tính như sau:   " # 1 0 0 0 1 · S1 0 · S1 1 1 0 0   S2 = S1 ⊗ S1 = = 1 · S1 1 · S1  1 0 1 0 1 1 1 1   1 1 1      " #  1 0 1    1 · S2 0 · S2 1 1 1 1  S3 = S1 ⊗ S2 = =  1 · S2 1 · S2 1  0 0 0 1   1 1 0 0 1 1      1 0 1 0 1 0 1  1 1 1 1 1 1 1 1 Do đó, lấy giới hạn limn→∞ Sn ta thu được tam giác Sierpinski S.
15 Một công thức ma trận tam giác Sierpinski khác ít được biết đến hơn là công thức ma trận suy rộng một tham số của tam giác Sierpinski theo hàm tổng kí tự được đưa ra bởi Callan [1]. Nếu ta định nghĩa " # 1 0 S1 (x) = (1.17) x 1 và Sn+1 (x) = S1 (x) ⊗ Sn (x) (1.18) với n > 1, khi đó   1 x 1    x 0 1     2  x x x 1    x S(x) := lim Sn (x) =  0 0 0 1 (1.19)  n→∞   x2 x 0 0 x 1     x2 0 x 0 x 0 1     3 x2 x2 1 x2 x x 1  x  ... ··· Vì Sn (1) = Sn nên S(1) = S. Nếu ta ký hiệu S(x) = [sjk (x)] và giả sử các chỉ số j, k là số không âm và (j, k) = (0, 0) là chỉ số của số trên cùng bên trái, khi đó các phần tử sjk (x) được xác định bởi ( xs(j−k) nếu 0 ≤ k ≤ j và (k, j − k) là carry-free sjk (x) = (1.20) 0 nếu ngược lại. Để chỉ ra (1.20) miêu tả đúng (1.19), ta sử dụng phép quy nạp. Chứng minh. Rõ ràng S1 (x) thỏa mãn (1.20). Tiếp theo, giả sử Sn (x) thỏa mãn (1.20). Ta cần chỉ ra mọi phần tử sjk (x) của Sn+1 (x) cũng thỏa mãn (1.20). Để chứng minh điều này, lưu ý rằng Sn+1 (x) có cỡ 2n+1 ×2n+1 . Ta chia Sn+1 (x) thành 4 ma trận con A, B, C, D, mỗi ma trận có cỡ 2n × 2n , dựa vào hệ thức truy hồi " # " # Sn (x) 0 A B Sn+1 (x) = = , xSn (x) Sn (x) C D trong đó A = D = Sn (x), B = 0 và C = xSn (x). Ta xét bốn trường hợp phụ thuộc vào phần tử sjk (x) thuộc ma trận con nào.
16 Trường hợp 1: 0 ≤ j, k ≤ 2n − 1. Khi đó sj,k thuộc A = Sn (x) và do đó (1.20) đúng. Trường hợp 2: 0 ≤ j ≤ 2n − 1, 2n ≤ k ≤ 2n+1 − 1. Khi đó sjk (x) thuộc B = 0, hay sjk (x) = 0 và do đó (1.20) đúng vì k ≥ j. Trường hợp 3: 2n ≤ j, k ≤ 2n+1 − 1. Khi đó sjk (x) thuộc D = Sn (x). Gọi j = j0 20 + · · · + jn 2n , k = k0 20 + · · · kn 2n là biểu diễn nhị phân của j, k. Ta thấy jn = kn = 1. Đặt j 0 = j = 2n , k 0 = k − 2n , tức là ta xóa kí tự jn khỏi j và kn khỏi k . Khi đó, cặp (k, j − k) là carry-free khi và chỉ khi với cặp (k 0 , j 0 − k 0 ). Ngoài ra, s(j − k) = s(j 0 − k 0 ). Ta kết luận được 0 0 sjk (x) = sj 0 k0 = xs(j −k ) = xs(j−k) nên (1.20) đúng. Trường hợp 4: 2n ≤ j ≤ 2n+1 − 1, 0 ≤ k ≤ 2n − 1. Khi đó sjk (x) thuộc C = xSn (x). Định nghĩa j 0 = j − 2n và k 0 = k. Một lần nữa, cặp (k, j − k) là carry-free khi và chỉ khi (k 0 , j 0 − k 0 ) là carry-free. Ngoài ra, s(j − k) = s(2n + j 0 − k 0 ) = 1 + s(j 0 − k 0 ). Do đó, 0 0 sjk (x) = xsj 0 k0 = x1+s(j −k ) = xs(j−k) nên (1.20) đúng. Điều phải chứng minh. Định lý 1.4.3 ([1]). Ma trận S(x) thỏa mãn S(x)S(y) = S(x + y). (1.21) Pi Chứng minh. Giả sử i ≥ j. Số hạng ở vị trí (i, j) của S(x)S(y) là k=j sik (x)skj (y). Với 0 ≤ k ≤ i, nếu i − k là tự do của k thì cả hai số đều có kí tự 0 tại các trị trí mà i có số 0. Các kí tự của k tương ứng với những vị trí mà i có 1 là tùy ý, nên i − k có ký tự đối tại những vị trí này. Ví dụ, với i = 1011112 , k có dạng a0bcde, khi đó i − k = a0 0b0 c0 d0 e0 . Ngoài ra, nếu k ≥ j và k − j là tự do của j thì các kí tự của k bị ràng buộc thêm: chúng là kí tự 1 tại mỗi vị trí mà j có 1. Tổng kết lại, nếu i − k là tự do của k và jk − j là tự do của j thì k phải có các kí tự 0 tại vị trí i có 0 và có các kí tự 1 tại vị trí j có 1 và không bị ràng buộc tại tại các vị trí i có 1 và j có 0. Nói riêng, sự tồn tại của k ∈ [i, j] với i − k tự do với k và
17 k − j tự do với j kéo theo i phải có 1 tại vị trí j có 1 và suy ra j − j tự do với Pi j. Do đó, nếu i − j không tự do với j thì (S(x)S(y))ij = k=j 0 = 0 = sij (x + y). Mặt khác, nếu i − j tự do với j , giả sử có t (≥ 0) vị trí mà i có 1 và j có 0 (và do đó s(i − j) = t). Như bên trên, các số k ∈ [j, i] thỏa mãn i − k tự do với k và k − j tự do với j không bị giới hạn tại các vị trí này và cả i − k và k − j đều có 0 tại các vị trí còn lại. Do đó, ta có i 0 0 X X (S(x)S(y))ij = sik (x)skj (y) = xi1 +···it y i1 +···+it k=j (i1 ,...,it )∈{0,1}t t X t = xm y t−m = (x + y)t = sij (x + y) m m=0 (trong đó a0 là kí tự đối của a trong hệ nhị phân, tức là a0 = 1 − a). Định lý được chứng minh. Ta sẽ thấy tính chất (1.21) kéo theo dạng số hóa của định lý nhị thức. Ví dụ 1.4.4. Cân bằng số hạng s30 của ma trận S(x + y) với số hạng tương ứng của tích ma trận S(x)S(y) ta thu được đẳng thức s30 (x + y) = s30 (x)s00 (y) + s31 (x)s10 (y) + s32 (x)s20 (y) + s33 (x)s30 (y) + 0 ⇔ (x + y)s(3) = xs(3) y s(0) + xs(2) y s(1) + xs(1) y s(2) + xs(0) y s(3) . (1.22) Đối chiếu với các giá trị s(k) đã được tính trong Ví dụ 1.2.7, (1.22) chính là định lý nhị thức với n = 2: (x + y)2 = x2 + 2xy + y 2 . Ví dụ 1.4.5. Cân bằng số hạng s50 của ma trận S(x + y) với số hạng tương ứng của tích ma trận S(x)S(y) ta thu được đẳng thức s50 (x + y) = s50 (x)s00 (y) + s51 (x)s10 (y) + s52 (x)s20 (y) + s53 (x)s30 (y) + s54 (x)s40 (y) + s55 (x)s50 (y) + 0 ⇔ (x + y)s(5) = xs(5) y s(0) + xs(4) y s(1) + 0y s(2) + 0y s(3) + xs(1) y s(4) + xs(0) y s(5) ⇔ (x + y)s(5) = xs(5) y s(0) + xs(4) y s(1) + xs(1) y s(4) + xs(0) y s(5) . (1.23) Đối chiếu với các giá trị s(k) đã được tính trong Ví dụ 1.2.7, (1.23) chính là định lý nhị thức với n = 2: (x + y)2 = x2 + 2xy + y 2 .
18 Ví dụ 1.4.6. Cân bằng số hạng s70 của ma trận S(x + y) với số hạng tương ứng của tích ma trận S(x)S(y) ta thu được đẳng thức s70 (x + y) = s70 (x)s00 (y) + s71 (x)s10 (y) + s72 (x)s20 (y) + s73 (x)s30 (y) + s74 (x)s40 (y) + s75 (x)s50 (y) + s76 (x)s60 (y) + s77 (x)s70 (y) + 0 ⇔ (x + y)s(7) = xs(7) y s(0) + xs(6) y s(1) + xs(5) y s(2) + xs(4) y s(3) + xs(3) y s(4) + xs(2) y s(5) + xs(1) y s(6) + xs(0) y s(7) . (1.24) Đối chiếu với các giá trị s(k) đã được tính trong Ví dụ 1.2.7, (1.24) chính là định lý nhị thức với n = 3: (x + y)3 = x3 + x2 y + x2 y + xy 2 + x2 y + xy 2 + xy 2 + y 3 = x3 + 3x2 y + 3xy 2 + y 3 .