i
Mục lục
Mục lục i
Lời cảm ơn ii
Một số ký hiệu iii
Mở đầu 1
1 Kiến thức chuẩn bị 2
1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Một vài loại số đặc biệt 9
2.1 Số Stirling . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Số Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Số Harmonic . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Số Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 Ứng dụng trong toán phổ thông . . . . . . . . . . . . . . . . 51
2.5.1 Ứng dụng của số Fibonacci . . . . . . . . . . . . . . 51
2.5.2 Ứng dụng của số Stirling . . . . . . . . . . . . . . . 53
Kết luận 58
Tài liệu tham khảo 59
ii
Lời cảm ơn
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. Tác giả xin bày tỏ lòng biết ơn sâu sắc với PGS.TS. Nông Quốc
Chinh, đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời
gian nghiên cứu vừa qua.
Xin chân thành cảm ơn tới các thầy, cô giáo trong Khoa Toán - Tin, Phòng
Đào tạo, các bạn học viên lớp Cao học Toán K7D trường Đại học Khoa học
- Đại học Thái Nguyên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi,
động viên tác giả trong quá trình học tập và nghiên cứu tại trường.
Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân
luôn khuyến khích, động viên tác giả trong suốt quá trình học tập và làm luận
văn.
Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót
và hạn chế. Tác giả mong nhận được những ý kiến đóng góp quý báu của các
thầy cô và bạn đọc để luận văn được hoàn thiện hơn.
Thái Nguyên, 2015 Nguyễn Công Còn
Học viên Cao học Toán K7D,
Trường ĐH Khoa học - ĐH Thái Nguyên
iii
Một số ký hiệu
k =
n C n Tổ hợp chập k của n k n Số Stirling loại 1
n k Số Stirling loại 2
(cid:42) k (cid:43) n Số Euler bậc 1 k
(cid:42) (cid:43)(2) n Số Euler bậc 2 k
Số Harmonic thứ n Hn
Số Fibonacci thứ n Fn
1
Mở đầu
Số học luôn được mệnh danh là nữ hoàng của toán học, bởi trong nó chứa
đựng nhiều vẻ đẹp của tư duy logic. Việc nghiên cứu các loại số có tính chất
đặc biệt như số nguyên tố, số Bernoulli, số Hoàn hảo, .v.v. . . luôn là một đề
tài hấp dẫn đối với những người yêu toán xưa và nay. Mục tiêu của luận văn
này là trình bày một số kết quả về một vài số đặc biệt đó là số Stirling, số
Euler, số Harmonic, số Fibonacci và một vài ứng dụng của chúng trong toán
phổ thông.
Luận văn được trình bày thành 2 chương chính với nội dung cụ thể là:
Chương 1 trình bày các kiến thức cơ bản có liên quan cần sử dụng cho
chương 2.
Chương 2 trình bày các khái niệm, tính chất, định lý, hệ quả về các số
Stirling, Euler, Harmonic, Fibonacci và một số công thức biểu thị mối quan
hệ giữa các số đó, ứng dụng của chúng trong toán phổ thông. Sau một thời
gian nghiên cứu luận văn đã được hoàn thành.
Mặc dù tác giả đã hết sức cố gắng, tuy nhiên luận văn vẫn không tránh
khỏi những sai sót, tác giả xin tiếp thu các ý kiến góp ý của các thầy cô giáo
và các bạn đồng nghiệp. Chúng tôi xin chân thành cảm ơn.
Thái Nguyên, ngày 20 tháng 11 năm 2015
Nguyễn Công Còn
Email: nguyencongcon@gmail.com
2
Chương 1
Kiến thức chuẩn bị
1.1 Định nghĩa và ví dụ
n Định nghĩa 1.1.1. Số tập con có k phần tử của tập n phần tử, kí hiệu k
và được gọi là tổ hợp chập k của n.
Ví dụ 1.1.1. Có 6 tập con có 2 phần tử của tập {1, 2, 3, 4} đó là
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. 4 Do vậy = 6. 2
Định lí 1.1.1. Cho n, k là các số nguyên dương và 0 ≤ k ≤ n. Khi đó
n! (1.1) n = . k!.(n − k)! k
Chứng minh. Đầu tiên, tính số dãy có k phần tử: có n cách chọn phần tử thứ
nhất, có n − 1 cách chọn phần tử thứ hai, ..., có n − k + 1 cách chọn phần tử
thứ k. Do vậy có tất cả n(n − 1) . . . (n − k + 1) cách chọn. Vì mỗi tập con có
k phần tử có k! cách sắp thứ tự khác nhau. Do đó
n! n(n − 1) . . . (n − k + 1) = n = k! . k!.(n − k)! k
3
1.2 Một số tính chất
Định lí 1.2.1. Cho n và k là các số nguyên bất kì sao cho 0 ≤ k ≤ n. Khi đó n (1.2) . n = n − k k
Chứng minh. Theo định lý 1.1.1, ta có
n! (n − k)! n = = n = . k!(n − k)! (n − (n − k))! k n − k
n Đặc biệt n = n = = n. 0 n = 1 và n 1 n − 1
Định lí 1.2.2. Công thức truy hồi n n − 1 n − 1 (1.3) = + , n, k > 0. k k − 1 k
Chứng minh. Ta có (n − 1)! (n − 1)! n − 1 n − 1 + = + (n − k)!(k − 1)! (n − k − 1)!k! k k − 1
(n − 1)!k (n − 1)!(n − k) + = (n − k)!k! (n − k)!k!
(n − 1)![k + (n − k)] = (n − k)!k!
n! (n − 1)!n = = (n − k)!k! (n − k)!k!
= n . k
Định lý được chứng minh.
4
Định lí 1.2.3 (Định lý nhị thức).
n (cid:88)
k=0
(x + y)n = (1.4) n xn−kyk. k
Chứng minh. Chứng minh bằng quy nạp trên n. Dễ dàng kiểm tra định lý
đúng với n = 0, 1, 2.
Giả sử định lý đúng với n − 1, tức là
n−1 (cid:88)
k=0
n − 1 (x + y)n−1 = xn−1−kyk. k
Từ giả thiết quy nạp và (1.3), ta có
(x + y)n = (x + y)(x + y)n−1
n−1 (cid:88)
k=0
n − 1 = (x + y) xn−1−kyk k
n−1 (cid:88)
n−1 (cid:88)
k=0
n − 1 n − 1 = x xn−1−kyk xn−1−kyk + y k k
k=0
n−1 (cid:88)
n−1 (cid:88)
k=0
k=0
n − 1 n − 1 = xn−1−kyk+1 xn−kyk + k k
n (cid:88)
n−1 (cid:88)
k=0
n − 1 n − 1 = xn−kyk + xn−kyk k − 1 k
n−1 (cid:88)
n (cid:88)
k=1 xn−kyk +
k=1
k=1
(cid:19) n − 1 n − 1 = xn + xn−kyk (cid:18)n − 1 0 k k − 1
n−1 (cid:88)
k=1
(cid:19) + yn (cid:18)n − 1 n − 1 (cid:19) (cid:19) n − 1 n − 1 xn + yn = + xn−kyk + (cid:18)n − 1 0 (cid:18)n − 1 n − 1 k k − 1
5
n−1 (cid:88)
k=1
(cid:19) (cid:19) = yn xn + n xkyk + (cid:18)n − 1 n − 1 (cid:18)n − 1 0 k
n−1 (cid:88)
k=1
(cid:19) (cid:19) yn = xn + n xn−kyk + (cid:18)n n (cid:18)n 0 k
n (cid:88)
k=0
= n xn−kyk. k
k
Sau đây là bảng các giá trị của (cid:0)n (cid:1) với 0 ≤ k, n ≤ 10 và được gọi là tam
giác Pascal.
n n n n n n n n n n 0 1 2 3 4 5 6 7 8
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 21 1
8 1 8 28 56 70 56 28 8 1
Bảng 1.1: Tam giác Pascal.
6
n (cid:88)
Hệ quả 1.2.1.
k=0
(1.5) n = 2n. k
Chứng minh. Theo (1.4) với x = y = 1.
n (cid:88)
Hệ quả 1.2.2.
k=0
(−1)k (1.6) n = 0. k
Chứng minh. Theo (1.4) với x = 1 và y = −1.
Định lí 1.2.4. Với 0 ≤ k ≤ n, ta có
n − 1 k (1.7) . n = n k k − 1
Chứng minh. Ta có
n! (n − 1)! n − 1 k = n = n n = k . k!(n − k)! (k − 1)!(n − k)! k k − 1
Định lí 1.2.5. Với 0 ≤ k ≤ m ≤ n, ta có
n m n n − k (1.8) = . m k k m − k
Chứng minh. Ta có
m! n! n m = . m!(n − m)! k!(m − k)! m k
n! = k!(n − m)!(m − k)!
7
n! (n − k)! = (n − m)!(m − k)! . k!(n − k)! n − k n = . m − k k
n (cid:88)
k=0
Định lí 1.2.6. n + 1 k (1.9) . = c + 1 c
Chứng minh. Với n = 0 dễ thấy định lý đúng.
n−1 (cid:88)
k=0
Giả sử với n ≥ 1 thì n k . = c + 1 c
Khi đó
n−1 (cid:88)
n (cid:88)
k=0
n k k + = c c c
k=0
n n = + c c + 1
n + 1 = . c + 1
n (cid:88)
k=0
Định lí 1.2.7. r + k r + n + 1 (1.10) = . k n
Chứng minh. Ta có
n (cid:88)
n (cid:88)
k=0
k=0
r + k r + k = (theo 1.2) k r
8
r + n + 1 = (theo 1.9) r + 1
r + n + 1 = (theo 1.2). n
Định lí 1.2.8 (Đẳng thức Vandermonde). Cho m, n và r là các số nguyên
không âm sao cho r ≤ m và r ≤ n. Khi đó
r (cid:88)
k=0
(cid:19) (cid:19)(cid:18) n = (cid:19) . (1.11) (cid:18)m k r − n (cid:18)m + n r
Chứng minh. Phân hoạch tập S gồm m + n phần tử thành hai tập con T có
m phần tử và tập U có n phần tử. Chọn r phần tử từ S, k phần tử tử T và còn
lại phần tử từ U .
n (cid:88)
k=0
Định lí 1.2.9. (cid:19)2 (cid:19) = . (cid:18)n k (cid:18)2n n
Chứng minh. Theo (1.2) và (1.11), ta có
n (cid:88)
n (cid:88)
k=0
k=0
(cid:19)2 (cid:19) (cid:19) (cid:19)(cid:18) n = = . (cid:18)n k (cid:18)n k n − k (cid:18)2n n
9
Chương 2
Một vài loại số đặc biệt
2.1 Số Stirling
Định nghĩa 2.1.1. Số phân hoạch một tập hợp có n phần tử thành k tập con
n khác rỗng gọi là số Stirling loại 2 và kí hiệu là k .
n = 0 với mọi n ∈ N∗; Quy ước:
0 0 = 0 với mọi k ∈ N∗; k
n 0 = 1. = 0 nếu k > n và k 0
Ví dụ 2.1.1. Có 7 cách phân hoạch một tập có 4 phần tử {1, 2, 3, 4} thành 2
tập con khác rỗng, đó là
{1, 2, 3} ∪ {4} {1, 2, 4} ∪ {3} {1, 3, 4} ∪ {2} {2, 3, 4} ∪ {1}
{1, 2} ∪ {3, 4} {1, 3} ∪ {2, 4} {1, 4} ∪ {2, 3}.
4 Do đó = 7. 2
10
Mệnh đề 2.1.1. Cho n, k là các số nguyên dương. Khi đó
n n − 1 n − 1 . + = k (2.1) k k − 1 k
Chứng minh. Kí hiệu [n] là tập gồm n phần tử.
Vì mỗi cách phân hoạch [n] thành k tập con khác rỗng có thể ta thu được từ
một phân hoạch [n − 1] thành k tập con khác rỗng, sau đó bổ sung phần tử n
vào một trong k tập con khác rỗng đó.
Với mỗi cách chia tập [n − 1] thành k tập con khác rỗng, ta có k cách bổ
n − 1 sung phần tử thứ n vào một trong k tập con đó, nên ta có cách phân k
hoạch. Mặt khác ta có thể chia tập [n] thành k tập con khác rỗng bằng cách
chia tập [n − 1] thành (k − 1) tập con, sau đó bổ sung thêm một tập con nữa
n − 1 cách có đúng một phần tử {n} để nhận được k tập con. Ta sẽ có k − 1
phân hoạch kiểu này. Vì vậy
n − 1 n − 1 n . + = k k − 1 k k
Từ công thức (2.1) của mệnh đề 2.1.1 ta nhận được tam giác số Stirling
loại 2 như sau:
Định lí 2.1.1. Với mọi số nguyên n ≥ 2, ta có
n = 2n−1 − 1. (2.2) 2
2 2 = 21 − 1 Chứng minh. Với n = 2 ta có = 1 = 21 − 1. Vậy 2 2
(đúng).
11
n n n n n n n n n n
8 7 6 5 4 3 2 1 0
0 1
1 0 1
2 0 1 1
3 0 1 3 1
1 4 0 1 7 6
10 5 0 1 15 25 1
65 6 0 1 31 90 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
Bảng 2.1: Bảng số Stirling loại 2.
k = 2k−1 − 1, ta chứng Giả sử đẳng thức đúng với n = k > 2, tức là 2
minh đẳng thức đúng với n = k + 1, thật vậy:
k + 1 k k = + 2 2 1 2
= 1 + 2(2k−1 − 1)
= 1 + 2k − 2 = 2(k+1)−1 − 1.
Vậy bài toán được chứng minh.
4 = 24−1 − 1 = 7. Trở lại định lý 2.1.1, ta thấy 2
12
Định lí 2.1.2. Số Stirling loại 2 có thể tính trực tiếp qua công thức sau:
k (cid:88)
i=0
(cid:19) 1 n (−1)k−i = in. (2.3) k! (cid:18)k i k
Chứng minh. Gọi N và K là hai tập hợp với |N | = n, |K| = k, H là tập con
của K và f (H) là số ánh xạ từ N tới K\H.
Thay i = k − j, ta có
n k!. = {f : N → K|f là toàn ánh} k
H⊆K
k (cid:88)
(cid:88) = (−1)|H|f (H)
j (k − j)n
j=0
k (cid:88)
= (−1)jC k
j (i)n.
i=0
= (−1)k−iC k
Ví dụ 2.1.2. Ta có
2 (cid:88)
j=0
(cid:19) 1 4 i4(−1)2−i = (cid:18)2 i 2! 2
(cid:19) (cid:19) = 04(−1)2−0 + 14(−1)2−1 + (cid:19) 24(−1)2−2(cid:105) (cid:18)2 1 (cid:18)2 2 (cid:104)(cid:18)2 1 0 2
= 1 [1.0.1 + 2.1.(−1) + 1.16.1] = 7. 2
Định lí 2.1.3. Cho n và m là các số nguyên không âm. Ta có
n (cid:88)
k=0
n + 1 k (cid:19) . = . (2.4) (cid:18)n k m + 1 m
13
k
k Chứng minh. Phân hoạch n + 1 số nguyên 1, . . . , n + 1 thành m + 1 tập con, (cid:1) cách chọn n − k số nguyên khác nhau thành một tập con và ta có (cid:0)n m
cách phân hoạch k số còn lại thành m tập con. Vậy ta có đẳng thức cần chứng
minh.
Ví dụ 2.1.3. a) Ta có
n (cid:88)
k=1
n + 1 n + 1 k = = (cid:19) . (cid:18)n k 2 1
k=1
(cid:19) n (cid:88) = = 2n − 1. 1 + 1 (cid:18)n k
b) Ta có
4 (cid:88)
k=2
k 5 = (cid:19) . (cid:18)4 k 2 3
4 3 2 + (cid:19) . + (cid:19) . = (cid:19) . (cid:18)4 4 (cid:18)4 3 (cid:18)4 2 2 2 2
= 6.1 + 4.3 + 1.7 = 25.
n (cid:88)
k=0
k n + 1 Định lí 2.1.4. Cho n và m là các số nguyên không âm. Ta có = (m + 1)n−k . (2.5) m + 1 m
Chứng minh. Ta chứng minh bằng quy nạp. Công thức trên hiển nhiên đúng
khi n = 0. Giả sử
n−1 (cid:88)
k=0
n k = (m + 1)n−k−1 m + 1 m
n + 1 n n Khi đó ta có = + (m + 1) m + 1 m m + 1
14
n−1 (cid:88)
k=0
k n (m + 1)n−k−1 + (m + 1) = m m
n−1 (cid:88)
k=0
k n (m + 1)n−k = + m m
n (cid:88)
k=0
k (m + 1)n−k . = m
Định lý được chứng minh.
4 (cid:88)
k=2
k Ví dụ 2.1.4. Ta có 5 = 34−k. 2 3
4 3 2 + 34−4. + 34−3. = 34−2.
2 2 2
= 32.1 + 31.3 + 30.7 = 25.
Định lí 2.1.5. Cho n và m là các số nguyên không âm. Ta có
m (cid:88)
k=0
n + m n + m + 1 . = k (2.6) m m
Chứng minh. Chứng minh bằng quy nạp. Công thức hiển nhiên đúng với
n ≥ 0 khi m = 0.
Giả sử
m−1 (cid:88)
k=0
n + m n + m = k , ∀n ≥ 0. m − 1 m
Khi đó, ta có
n + m + 1 n + m n + m = + m m m − 1 m
15
m−1 (cid:88)
k=0
n + m n + k + m k = m k
m (cid:88)
k=0
n + k . k = k
Định lý được chứng minh.
Tiếp theo ta tìm hiểu về số Stirling loại 1. Trước hết ta định nghĩa về chu
trình:
Chu trình là một hoán vị vòng tròn, giống như dây chuyền. Chu trình
có thể viết như [A, B, C, D] với cách hiểu là
[A, B, C, D] = [B, C, D, A] = [C, D, A, B] = [D, A, B, C].
Mặt khác, chu trình [A, B, C, D] khác [A, B, D, C] hoặc [D, C, B, A].
Định nghĩa 2.1.2. Cho n và k là các số nguyên khác không, n ≤ k. Số
Stirling loại 1 ký hiệu n là số cách sắp xếp (số hoán vị) n phần tử thành k k
chu trình khác nhau.
Ví dụ 2.1.5. * Tập X = {1, 2, 3, 4} có thể sắp xếp thành 2 chu trình như sau:
(123)(4), (124)(3), (134)(2), (234)(1), (132)(4), (142)(3),
(243)(1), (12)(34), (13)(24), (14)(23). (143)(2),
Vậy = 11. 4 2
16
* Số cách sắp xếp 4 phần tử thành 3 chu trình là
(1)(2)(34), (1)(3)(24), (1)(4)(23),
(2)(3)(14), (2)(4)(13), (3)(4)(12).
Vậy = 6. 4 3
* Số cách sắp xếp 4 phần tử thành 1 chu trình là
(1234), (1324), (1423), (2314), (2413), (3412).
Vậy = 6. 4 1
* Số cách sắp xếp 4 phần tử thành 4 chu trình là
1 2 3 4 {(1)(2)(3)(4)} = 1 2 3 4
Đây chính là hoán vị đồng nhất của X. Vậy = 1. 4 4
Định lí 2.1.6. Cho n > 0 là số nguyên, khi đó ta có
n − 1 n − 1 (2.7) . + n = (n − 1) k − 1 k k
Chứng minh. Xét việc lập một hoán vị của n + 1 phần tử từ n phần tử bằng
cách thêm vào một phần tử sao cho hoán vị đó có k chu trình. Có hai cách:
• Lập một chu trình đơn chỉ gồm một phần tử mới thêm vào. Khi đó còn
lại k − 1 chu trình lập từ n phần tử, có (n, k − 1) chu trình.
• Chèn phần tử mới đó vào một trong các chu trình đã có. Xét hoán vị bất
kì của n phần tử a1a2 . . . an trong đó có k chu trình:
(a1, . . . , aj1)(aj1+1, . . . , aj2) . . . (ajk−1+1, . . . , an) (cid:124) (cid:125) (cid:123)(cid:122) k chu trình
17
Để lập một hoán vị mới của n + 1 phần tử với k chu trình, ta cần chèn phần tử
mới đó vào một trong k chu trình này. Có n cách chèn phần tử mới vào trong n dãy n phần tử đó. Từ đó có n. cách. Tổng của hai giá trị ứng với hai khả k
năng trên cho ta kết quả cần chứng minh.
Từ công thức (2.7) của mệnh đề 2.1.6 ta nhận được tam giác số Stirling
loại 1 như sau:
n n n n n n n n n n 1 2 3 4 5 6 7 8 0
0 1
1 0 1
2 0 1 1
3 0 2 3 1
4 0 6 11 6 1
5 0 24 50 35 10 1
6 0 120 274 225 85 15 1
7 0 720 1764 1624 735 175 21 1
8 0 5040 13068 13132 6769 1960 322 28 1
Bảng 2.2: Bảng số Stirling loại 1.
Định lí 2.1.7. Với mỗi số nguyên n > 0 ta có
(2.8) n = (n − 1)!. 1
18
Chứng minh. Ta chứng minh bằng phương pháp quy nạp.
Định lý đúng với n = 1.
Định lý đúng với n = 2.
Giả sử định lý đúng tới n = t, ta chứng minh định lý đúng tới n = t + 1.
Thật vậy, ta có t t + 1 = t.(t − 1)! = t!. = t. 1 1
Định lý được chứng minh.
n Nhận xét: Với mọi n, k ≥ 0, k ≤ n ta có n ≥ k k .
Định lí 2.1.8. Cho n là một số nguyên dương. Khi đó
n (cid:88)
k=0
(2.9) n = n!. k
Chứng minh. Trường hợp khi n = 0 là đúng vì = 1 = 0!. 0 0
Bây giờ ta giả sử rằng công thức đúng tới n > 0. Tức là
n (cid:88)
k=0
n = n!. k
Ta có
n+1 (cid:88)
n+1 (cid:88)
k=0
k=0
n + 1 n n = + n k
n+1 (cid:88)
n+1 (cid:88)
k=0
k=0
k − 1 k n n = + n k − 1 k
n+1 (cid:88)
n+1 (cid:88)
k=1
k=0
n n = + n k − 1 k
19
n+1 (cid:88)
n (cid:88)
k=0
k=0
n n = + n k k − 1
= n! + n.n! = (n + 1)!.
Điều này kết thúc chứng minh định lý.
Ví dụ 2.1.6. Khi X = {1, 2, 3, 4} thì ta có
6 + 11 + 6 + 1 = 24 = 4!.
Định lí 2.1.9. Cho n là một số nguyên dương. Khi đó
n (cid:88)
j=0
n + 1 j. (2.10) n = . j 2
Chứng minh. Chứng minh bằng quy nạp. Với n = 1 thì
0. . = 0 + 1 = 1 = + 1. 2 2 1 1 1 0
Với n ≥ 2, giả sử rằng
n−1 (cid:88)
j=0
n − 1 j. n . = 2 j
Khi đó, theo công thức truy hồi (2.11) ta có
n (cid:88)
n (cid:88)
j=0
j=0
n − 1 n − 1 j. j. n = + (n − 1) j j
n (cid:88)
n (cid:88)
j=0
j=0
j − 1 n − 1 n − 1 j. = + (n − 1) j − 1 j
n (cid:88)
n (cid:88)
n (cid:88)
j=0
j=0
j=0
n − 1 n − 1 n − 1 j. = (j − 1) + + (n − 1) j − 1 j − 1 j
20
n (cid:88)
n (cid:88)
j=0
n − 1 n − 1 = (n − 1)! + (j − 1) + (n − 1) j
j=0
j − 1 n = (n − 1)! + n + (n − 1) 2
2
= n . n = n + n 2 2 1
Mệnh đề được chứng minh.
Ví dụ 2.1.7. Ta có
1. = 1.6 + 2.11 + 3.6 + 4.1 + 4. + 3. + 2. 4 4 4 3 4 2 4 1
= 50 = s(5, 2).
Định lí 2.1.10. Cho n và m là các số nguyên không âm. Khi đó
n (cid:88)
j=0
n + 1 (2.11) C j m. . n = m + 1 j
Chứng minh. Nếu m > n thì cả hai vế của đẳng thức đều bằng 0. Do đó, ta
giả sử m ≤ n.
(cid:19) . = 1.1 = 1 = (cid:18)0 0 Nếu n = 0 thì cho m = 0 ta có 0 0 1 . 1
Nếu n ≥ 1, giả sử với mọi k rằng
n−1 (cid:88)
j=0
n n − 1 (cid:19) . = . (cid:18)j k m j
21
Khi đó với mọi m ≤ n, công thức truy hồi Stirling chỉ ra
n (cid:88)
n (cid:88)
j=0
j=0
n − 1 n − 1 (cid:19) . (cid:19) . + (n − 1) n = (cid:18) j m (cid:18) j m j j
n (cid:88)
n (cid:88)
j=0
j − 1 (cid:19) n − 1 n − 1 . = (cid:19) . + (n − 1) (cid:18) j m (cid:18) j m j j − 1
j=0
n (cid:88)
j=0
n + 1 n − 1 = (cid:19) . + (n − 1). (cid:18) j m j − 1
n (cid:88)
j=0
m + 1 (cid:19) (cid:19)(cid:19) n n − 1 = . + + (n − 1). (cid:18)(cid:18) j − 1 m − 1 (cid:18)j − 1 m j − 1
n (cid:88)
n (cid:88)
j=0
j=0
m + 1 (cid:19) n − 1 n − 1 (cid:19) . = . + (cid:18)j − 1 m (cid:18) j − 1 m − 1 j − 1 j − 1
n + (n − 1). m + 1
n n n = + (n − 1).s + m
m + 1 m + 1 n + 1 n n = . = + n. m + 1 m + 1 m
Định l được chứng minh.
Ví dụ 2.1.8. Ta có
(cid:19) (cid:19) . . (cid:19) . (cid:19) . (cid:18)1 2 (cid:18)2 2 (cid:18)3 2 (cid:18)4 2 4 + 1 4 + 2 4 + 3
4 4
= 0.6 + 1.11 + 3.6 + 6.1 = 35 = . 5 3
22
Định lí 2.1.11. Cho n và m là các số nguyên không âm. Khi đó
m (cid:88)
k=0
n + m + 1 n + k (n + k). (2.12) . = k m
Chứng minh. Định lý rõ ràng đúng với mọi n ≥ 0 khi m = 0. Giả sử định lý
đúng tới m − 1, tức là
m−1 (cid:88)
k=0
n + k n + m (n + k). . = k m − 1
Theo công thức truy hồi (2.11), ta có
n + m n + m n + m + 1 + (n + m). = m m − 1 m
m−1 (cid:88)
k=0
n + k n + m = (n + k). + (n + m). k m
m (cid:88)
k=0
n + k = (n + k). . k
Định lý được chứng minh.
Nhận xét: Các số Stirling loại 1 và loại 2 có nhiều ý nghĩa trong cách biểu diễn trong cách biểu diễn lũy thừa của xn.
Đặt x0 = x0 x1 = x1
x2 = x(x − 1)
x3 = x(x − 1)(x − 2)
. . .
k−1 (cid:81) t=0
xk = x(x − 1)(x − 2) . . . (x − (k − 1)) = (x − t)
23
Định lí 2.1.12. Ta có
n (cid:88)
k=0
n xk. xn = (2.13) k
Chứng minh. Thực vậy, ta có thể chứng minh công thức (2.13) bằng phương
pháp quy nạp.
Với n = 0, n = 1 định lý hiển nhiên đúng.
Giả sử định lý đúng tới n − 1, nghĩa là
n−1 (cid:88)
k=0
n xn−1 = xk. k
Vì xk+1 = xk(x − k) nên ta có
xxk = xk+1 + kxk,
nên ta có
n−1 (cid:88)
n−1 (cid:88)
n − 1 n − 1 xn = x.xn−1 = x. xk = x.xk k k
k=0
k=0
n−1 (cid:88)
n−1 (cid:88)
k=0
n − 1 n − 1 k.xk = xk+1 + k k
k=0
n (cid:88)
n−1 (cid:88)
k=1
k=0
n − 1 n − 1 kxk = xk + k − 1 k
n n Vì = 0 với k < 0, n ≥ 0 và = 0 với k > n nên ta có thể bổ k k
n − 1 n − 1 sung thêm hai hạng tử vào tổng trên x0 = 0 và n.xn = 0. n 1
24
Khi đó từ tổng trên, ta có
n−1 (cid:88)
n (cid:88)
n − 1 n − 1 kxk xk +
k=1
k=0
n (cid:88)
k=1
n − 1 n − 1 k − 1 k (k. + = kxk) k − 1 k − 1
n (cid:88)
k=0
n = xk. k
Công thức được chứng minh.
Như vậy các hệ số biểu diễn xn qua các xi của công thức chính là các số
trong bảng 2.1 trên các dòng theo n.
Ta cũng có thể xây dựng theo phương pháp quy nạp theo n khái niệm xn
2 (cid:80) k=0
như sau: Đặt x0 = x0 x1 = x1 2 x2 = x2 + x1 + 0 = xk k
Bằng quy nạp ta chứng minh được
n (cid:88)
k=0
xn = n xk. k
Thật vậy, với n = 0 và n = 1 ta có
x0 = = 1 và x0 = + x. = 2. 0 0 1 0 1 1
Giả sử công thức đúng tới n = l − 1, tức là
l−1 (cid:88)
k=0
l − 1 xl−1 = xk. k
25
Với n = l, ta có
xl = xl−1(x + l − 1)
= x.xl−1 + (l − 1)xl−1
k≥0
l − 1 l − 1 (cid:88) (cid:88) = x xk xk + (l − 1) k k
k≥0
k≥0
k≥0
l − 1 l − 1 (cid:88) (cid:88) = xk xk+1 + (l − 1) k k
k≥1
k≥0
l − 1 l − 1 (cid:88) (cid:88) = xk xk + (l − 1)
k≥0
k − 1 l − 1 l − 1 (cid:88) = k xk + (l − 1) k
k≥0
l (cid:88) = k − 1 xk. k
n (cid:88)
Điều này suy ra
k=0
xn = (2.14) n xk. k
Định lí 2.1.13. Với n ≥ 0 là số nguyên, ta có
k
n (cid:88) xn = .(−1)n−k.xk. (2.15) k
k
(cid:88) xn = (2.16) n .(−1)n−k.xk. k
n (cid:88)
k=0
xn = (−1)n Chứng minh. Ta có xn = (−1)n(−x)n. Do đó n (−x)k k
26
n (cid:88)
k=0
= n .(−1)n−k.xk. k
n (cid:88)
k=0
Mệnh đề 2.1.2. Cho n và m là các số nguyên không âm. Khi đó n + 1 k nn−k. (2.17) = m + 1 m
Chứng minh. Rõ ràng công thức đúng với n = 0. Giả sử công thức đúng tới
n−1 (cid:88)
k=0
n − 1, tức là n + 1 k (n − 1)n−1−k. = m m
Theo công thức (2.11), ta có n n n + 1 + n. = m + 1 m m + 1
n−1 (cid:88)
k=0
n k = (n − 1)n−1−k. + n m m
n−1 (cid:88)
k=0
n k = nn−k. + m m
n (cid:88)
k=0
k nn−k. = . m
2.2 Số Euler
Định nghĩa 2.2.1. Cho n và k là các số nguyên không âm thỏa mãn k ≤ n. (cid:42) (cid:43) n Ta kí hiệu là số hoán vị π1π2 . . . πn của tập n số {1, 2, . . . , n} thỏa mãn k
27
trong hoán vị đó có k cặp số liền kề nhau tăng lên (nghĩa là πj < πj+1) và gọi
là số Euler tương ứng với cặp n, k.
(cid:43) (cid:42) 4 = 11. Vì có 11 hoán vị của {1, 2, 3, 4} có 2 cặp Ví dụ 2.2.1. a) Ví dụ 2
liền kề tăng
1324, 1423, 2314, 2413, 3412,
1243, 1342, 2341, 2134, 3124, 4123.
Dòng đầu là danh sách các hoán vị với π1 < π2 > π3 < π4, dòng thứ hai là
danh sách các hoán vị với π1 < π2 < π3 > π4 và π1 > π2 < π3 < π4.
b) Bảng các số Euler nhỏ nhất.
(cid:43) (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:43) (cid:42)n (cid:42)n n
2 3 4 5 6 7 8 1 0
0 1
0 1 1
1 2 1 0
4 3 1 1 0
11 4 1 11 1 0
26 5 1 66 26 1 0
57 6 1 302 302 57 1 0
7 1 120 1191 2416 1191 120 1 0
8 1 247 4239 15619 15619 4293 247 0 1
Bảng 2.3: Tam giác Euler.
28
Nhận xét: - Trong mỗi hoán vị π1, π2, . . . , πn có nhiều nhất (n − 1) cặp liền (cid:43) (cid:42) n = 0. kề nhau tăng, và do đó ta luôn có n
- Tam giác Euler cũng có tính chất đối xứng trong từng dòng giống như
trong tam giác Pascal, nhưng trong trường hợp tam giác Euler ta có
(cid:42) (cid:43) (cid:42) (cid:43) n n = . n − k − 1 n
Định lí 2.2.1. Với mọi n > 0, k ≤ n ta có:
(cid:43) (cid:43) (cid:42) (cid:42) n n . = (2.18) n − 1 − k k
Chứng minh. Số hoán vị của π1π2 . . . πn có n − 1 − k cặp liền kề nhau tăng
tương đương với số hoán vị của πn . . . π2π1 có k cặp liền kề nhau tăng.
Mỗi hoán vị π1, π2, . . . , πn có (n − 1) cặp số liền kề nhau, nếu hoán vị đó
có k cặp số liền nhau tăng thì sẽ có (n − 1 − k) cặp số liền nhau giảm, vì vậy
hoán vị viết theo thứ tự ngược lại là πn, πn−1, . . . , π2, π1 sẽ có (n − 1 − k) cặp
số liền nhau tăng. Do đó số hoán vị có k cặp số liền nhau tăng bằng số hoán
vị có (n − 1 − k) cặp số liền nhau tăng. Ta có điều phải chứng minh.
Từ Định lý trên ta có hệ quả sau.
Hệ quả 2.2.1. Với mọi n > 0, k ≤ n ta có:
k
(cid:42) (cid:43) n (cid:88) = n!. k
Mệnh đề 2.2.1. Với mọi n > 0, k ≤ n ta có:
(cid:42) (cid:43) (cid:42) (cid:43) (cid:42) (cid:43) n n − 1 n − 1 = (k + 1) − (n − k) . (2.19) k k k − 1
29
Chứng minh. Mỗi hoán vị ρ = ρ1 . . . ρn−1 của tập {1, . . . , n − 1} dẫn đến
n hoán vị của tập {1, 2, . . . , n} nếu ta thêm phần tử mới n trong tất cả
các cách có thể. Giả sử ta đặt n vào vị trí j và thu được hoán vị π =
ρ1 . . . ρj−1nρj . . . ρn−1. Số thứ tự tăng trong π là giống các số trong ρ, nếu j =
1 hoặc nếu ρj−1 < ρj; nó là một số lớn hơn các số trong ρ nếu ρj−1 > ρj hoặc (cid:42) (cid:43) n − 1 nếu j = n. Do đó π có k thứ tự tăng trong tổng (k +1) cách từ hoán k
(cid:43) (cid:42) n − 1 vị ρ mà có k thứ tự tăng, cộng với tổng của ((n − 2) − (k − 1) + 1)
k − 1 cách từ số hoán vị ρ mà có k − 1 thứ tự tăng. Suy ra công thức truy hồi là
(cid:42) (cid:43) (cid:42) (cid:43) (cid:42) (cid:43) n n − 1 n − 1 = (k + 1) − (n − k) . k k k − 1
Mệnh đề 2.2.2. Với mọi n > 0, k ≤ n ta có:
k
(cid:42) (cid:43) n (cid:88) xn = (cid:19) . (2.20) (cid:18)x + k . n k
(cid:42) (cid:43)(2) n , (0 ≤ k ≤ n − 1) là số hoán Định nghĩa 2.2.2. Số Euler bậc hai k
vị của tập {1, 1, 2, 2, . . . , n, n} với k thứ tự tăng lên mà có tính chất rằng với
mỗi j ∈ {1, 2, . . . , n}, các số nẵm giữa hai lần xuất hiện của j trong hoán vị
đều lớn hơn j.
Ví dụ 2.2.2. Với n = 3 có 15 hoán vị trong đó một không có thứ tự tăng lên,
tám hoán vị với một thứ tự tăng lên và sáu hoán vị với hai thứ tự tăng lên:
332211;
113322, 133221, 221331, 221133, 223311, 233211, 331122, 331221;
30
112233, 122133, 112332, 123321, 133122, 122331.
(cid:43)(2) (cid:43)(2) (cid:42) 3 (cid:43)(2) (cid:42) 3 (cid:42) 3 = 1, = 8, Do đó = 6. 0 1 2
Định lí 2.2.2. Các số Euler bậc hai thỏa mãn công thức truy hồi
(cid:43)(2) (cid:43)(2) (cid:42) (cid:42) (cid:42) n − 1 n − 1 (cid:43)(2) n . + (2n − 1 − k) = (k + 1) k − 1 k k
(2)
(2)
(2)
(2)
(2)
(2)
(2)
Bảng các số Euler loại 2.
(cid:43) (cid:43) (cid:43) (cid:43) (cid:43) (cid:43) (cid:43) (cid:42)n (cid:42)n (cid:42)n (cid:42)n (cid:42)n (cid:42)n (cid:42)n n
0 1 2 3 4 5 6
0 1
1 1 0
2 1 2 0
3 1 3 6 0
4 1 22 58 24 0
5 1 52 328 444 120 0
6 1 114 1452 4400 3708 720 0
Tương tự như các số Euler bậc một, ta có một số kết quả sau.
Mệnh đề 2.2.3. Cho số nguyên n ≥ 0, Khi đó
k
(cid:42) (cid:19) x (cid:43)(2) n (cid:88) = . (cid:18)x + n − 1 − k . 2n x − n k
31
Mệnh đề 2.2.4. Cho số nguyên n ≥ 0. Khi đó
k
(cid:42) (cid:43)(2) n x (cid:88) (cid:19) . = (cid:18)x + k . 2n k x − n
Định lí 2.2.3.
t1+t2+···+tk+1=n−k−1 tj≥0, j=1,2,...,k+1
(cid:42) (cid:43)(2) n (cid:88) = 1t12t2 . . .(k + 1)tk+1(2t1 + 2)[2(t1 + t2) + 3] . . . k
. . . [2(t1 + · · · + tk) + (k + 1)].
Ví dụ 2.2.3.
t1+t2+t3=2 tj≥0, j=1,2,3
(cid:43)(2) (cid:42) 5 (cid:88) = 1t12t23t3(2t1 + 2)[2(t1 + t2) + 3] 2
= 122030(4 + 2)(4 + 3) + 102230(0 + 2)(4 + 3) + 102032(0 + 2)(0 + 3)
+ 112130(2 + 2)(4 + 3) + 112031(2 + 2)(2 + 3) + 102131(0 + 2)(3 + 3)
= 42 + 56 + 54 + 56 + 60 + 60
= 328.
Hệ quả 2.2.2. Cho n ≥ 1 là số nguyên. Khi đó
(cid:42) (cid:43)(2) n = n!; 1)
(cid:42) n − 1 (cid:43)(2) n = 2n+1 − 2(n + 1). 2) 1
32
2.3 Số Harmonic
Định nghĩa 2.3.1. Với mỗi số nguyên không âm n ta ký hiệu
n (cid:88)
k=1
1 1 1 1 + + · · · + = (n ≥ 0), (2.21) Hn = 1 + 2 3 n k
quy ước H0 = 0 và gọi Hn là số Harmonic thứ n.
Ví dụ 2.3.1. Một vài giá trị đầu tiên là
n 0 1 2 3 4 5 6 7 8 9 10
25 137 49 36 761 7129 7381 3 11 Hn 0 1 12 60 20 140 280 2520 2520 2 26
Nhận xét. Với n > 1 thì Hn không bao giờ là số nguyên.
Bổ đề 2.3.1. Cho p là một số nguyên tố lẻ. Khi đó
(2.22) Hp−k ≡ Hk−1 (mod p).
và
k − Hk,2) (mod p3).
p2 p − 1 (−1)k (H 2 (2.23) ≡ 1 − pHk + 2 k
p−1 (cid:88)
p−1 (cid:88)
với mọi k = 1, . . . , p − 1. Nếu p > 3 thì
k=1
k=1
≡ 0 (mod p). (2.24) Hk ≡ 1 − p (mod p3) và Hk−1 k
Chứng minh. Khi k ∈ {1, . . . , p − 1}, ta có
p−k (cid:88)
k−1 (cid:88)
k−1 (cid:88)
j=1
j=1
j=1
1 1 1 ≡ Hp−k = = Hp−1 − = Hk−1 (mod p). j p − k + j k − j
33
và
0 0 2 p p2 p p − 1 (cid:89) (cid:88) (cid:88) + (−1)k 1 − = ≡ 1 − j ij j k 0 0 0 1 p2 1 (cid:88) (cid:88) − ≡ 1 − pHk +
(mod p3).
2 j j2 Điều này chứng minh (2.22) và (2.23). Với đồng dư thứ nhất trong (2.24) ta thấy rằng p−1
(cid:88) p−1
(cid:88) k
(cid:88) p−1
(cid:88) p−1
(cid:88) j=1 k=1 k=1 k=1 k=j 1 1 = 1 Hk = j j p−1
(cid:88) j=1 p − j = = pHp−1 − (p − 1) ≡ 1 − p (mod p3). j vì Hp−1 ≡ 0 (mod p2). Bây giờ ta chứng minh đồng dư thứ hai trong (2.24). Lưu ý rằng p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) k=1 k=1 k=1 p p − 1 ≡ −p (mod p2). ≡ k 1 − pHk−1
k Hk−1
k k − 1 và do đó đồng dư thứ hai trong (2.24) được chứng minh. Bổ đề 2.3.2. Cho p > 3 là một số nguyên tố. Khi đó p(2) − 2qp(2) (mod p2). (2.25) H(p−1)/2 ≡ pq2 Chứng minh. Xem chứng minh trong [8]. p−1
(cid:88) p−1
(cid:88) Bổ đề 2.3.3. Cho p > 3 là một số nguyên tố. Khi đó k=1; 2(cid:45)k k=1; 2(cid:45)k ≡ ≡ − (mod p) (mod p) và (2.26) Hk
k q2
p(2)
2 Hk
k q2
p(2)
2 34 p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) Chứng minh. Theo (2.24), ta có k=1 k=1 k=1 = + Hk
k Hk−1
k 1
k2 ≡ 0 (mod p). Điều này suy ra đồng dư thứ nhất trong (2.26). Cho k ∈ {1, 2, . . . , p − 1} lẻ bất kỳ, rõ ràng (cid:19) (cid:19) − = (−1)k ≡ 1 − pHk (mod p2) (cid:18)p − 1
k (cid:18)p − 1
k theo (2.23). Do đó, từ (2.25) ta có p−1
(cid:88) p
(cid:88) p−1
(cid:88) k=1; 2|k k=0; 2|k k=1; 2|k (cid:1) (cid:19) 1 − 1 ≡ = + p (cid:18)p
k Hk−1
k 1 + (cid:0)p−1
k−1
k H(p−1)/2
2 p p(2) (mod p2),
q2 2p−1 − 1 p p = ≡ q2
p(2) − qp(2) + 2 2 p và do đó p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) k=1; 2|k k=1; 2|k k=1; 2|k
1 = + Hk−1
k Hk−1
k k2 (p−1)/2
(cid:88) k=1 1 1 ≡ + (mod p), ≡ q2
p(2)
2 8 1
k2 + (p − k)2 q2
p(2)
2 vì Hp−1,2 ≡ 0 (mod p). Bổ đề được chứng minh. Bổ đề 2.3.4. Cho n là một số nguyên dương bất kì. Khi đó n−1
(cid:88) n
(cid:88) k=0 k=1
2(cid:45)k 2k 1 = (2.27) n
. k + 1 k k 1
(cid:90) 1
(cid:90) Chứng minh. Ta có n−1
(cid:88) n−1
(cid:88) n−1
(cid:88) k=0 k=0 k=0 0 0 2k = 2k (2x)kdx xkdx = k + 1 35 1
(cid:90) 1
(cid:90) n
(cid:88) k=1 0 0 (2x)n − 1 dx = =
n
(2x − 1)k−1dx 2x − 1 k 1 n
(cid:88) n
(cid:88) 0 k=1 k=1 (2x − 1)k 1 − (−1)k n n = . = 2k 2k (cid:12)
(cid:12)
(cid:12)
(cid:12) k k 3 2 Do đó, bổ đề được chứng minh. 2n
(cid:88) n
(cid:88) k=0 k=0 Bổ đề 2.3.5. Cho n ∈ N. Khi đó, ta có
2n 2n n = (−1)n (−1)k = (2.28) và (3n)!
(n!)3. k n k Chứng minh. Xem chứng minh trong [9]. p−1
(cid:88) Bổ đề 2.3.6. Cho p > 3 là một số nguyên tố. Khi đó k=1 (2.29) HkHk,2 ≡ 0 mod p). Chứng minh. Ta có p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) k
(cid:88) j=1 k=1 k=1 k=1 1 = Hk Hk 1
j2 = j2 p−1
(cid:88) j=1
(cid:32) p−1
(cid:88) 0 j=1 j=1 (cid:33) 1 (cid:88) = Hk − Hs j2 p−1
(cid:88) s
(cid:88) p−1
(cid:88) t=1 0 j=1 k=1 1 1 (cid:88) = Hp−1,2 Hk − j2 t p−1
(cid:88) p−1
(cid:88) j=1 0 t≤s j=1 0 p−1
(cid:88) p−1
(cid:88) 1 1 1 j − t (cid:88) (cid:88) (cid:88) = − 1 = − j2 j2 t t j=1 k=1 = − ≡ − (mod p). jHj−1 − j + 1
j2 Hk−1
k Áp dụng đồng dư sau trong (2.24) ta được điều cần chứng minh. 36 2n−1
(cid:88) Bổ đề 2.3.7. Cho n ∈ N∗ ta có đẳng thức tổ hợp k=1 . (2.30) Hk = (−1)k−1
n
2(n + 1)2 + H2n
2n + 2 2n k Chứng minh. Xem chứng minh trong [10] trang 20. p−1
(cid:88) Định lí 2.3.1. Cho p > 3 là một số nguyên tố. Khi đó k=1 i) Hk
k2k ≡ 0 (mod p), p−1
(cid:88) k ≡ − k=1
p−1
(cid:88) 4 ii) k2H 2 (mod p), 9 k ≡ 6 (mod p), k=1
p−1
(cid:88) iii) H 3 k ≡ 2p − 2 (mod p2). k=1 iv) H 2 p−1
(cid:88) p−1
(cid:88) p−2
(cid:88) p−1
(cid:88) Chứng minh định lý 2.3.1. i) Ta có k=1 k=1 k=0 k=1 = − (mod p), Hk
k2k = Hp−k
(p − k)2p−k ≡ 2k−1Hk−1
−k 2kHk
k + 1 và do đó p−1
(cid:88) p−1
(cid:88) k=1 k=0 (cid:19) (cid:19) 2k (cid:18)(cid:18)p − 1 (cid:88) p (−1)k − 1 = (mod p), Hk
k2k ≡ k + 1 k trong đó p−2
(cid:88) p−2
(cid:88) k=0 k=0 (cid:19) 1 2k (cid:18) p (cid:88) := (−2)k − p k + 1 k + 1 p−1
(cid:88) p−1
(cid:88) j=1 k=1; 2(cid:45)k (cid:19) (cid:19) 1 1 = (−2)j − (theo bổ đề 2.3.4 ) −2p (cid:18)p
j k (cid:18)p − 1
k 37 p−1
(cid:88) k=1; 2(cid:45)k (1 − 2)p − 1 + 2p (cid:0)p−1
k = + . −2p (cid:1)(−1)k
k p−1
(cid:88) Do đó p−1
(cid:88) k=1; 2(cid:45)k k=1; 2(cid:45)k (cid:88) − p = Hp−1 − +qp(2) ≡ 1 − pHk
k H(p−1)/2
2 Hk
k p(2) ≡ qp(2) (mod p2),
q2 p ≡ − + H(p−1)/2
2 2 p−1
(cid:88) theo (2.25) và (2.26). Cuối cùng ta có k=1 (cid:88) p ≡ 0 (mod p2), Hk
k2k ≡ p−1
(cid:88) điều này suy ra k=1 Hk
k2k ≡ 0 (mod p). ii) Theo bổ đề 2.3.1 p−1
(cid:88) p−1
(cid:88) k ≡ k=0 k=0 (cid:18) (cid:19)(cid:19)2 k2 k2H 2 1 − (−1)k (mod p). p2 (cid:18)p − 1
k Nhớ lại rằng p−1
(cid:88) k=0 (p − 1)p(2p − 1) . k2 = 6 Hơn nữa p−1
(cid:88) p−1
(cid:88) k=0 k=0 (cid:19) (cid:19) (−1)kk2 = (−1)k(k + k(k − 1)) (cid:18)p − 1
k (cid:18)p − 1
k p−1
(cid:88) p−1
(cid:88) k=1 k=2 (cid:19) (cid:19) (−1)k−2 = (p − 1) (−1)k + (p − 1)(p − 2) (cid:18)p − 2
k − 1 (cid:18)p − 3
k − 2 = (1 − p)(1 − 1)p−2 + (p − 1)(p − 2)(1 − 1)p−3 = 0. 38 Do đó p−1
(cid:88) p−1
(cid:88) k ≡ k=0 k=0 (cid:19)2 p(p − 1)(2p − 1) k2 k2H 2 + p2 6 (cid:18)p − 1
k p−1
(cid:88) k=1 (cid:19)2 p (p − 1)2 ≡ (1 − 3p) + (mod p3). (cid:18)p − 2
k − 1 6 Từ (2.28) ta có p−1
(cid:88) p−2
(cid:88) j=0 k=1 (cid:19)2 (cid:19)2 (cid:19) (cid:19) p(p − 1) = = = 2(2p − 1)(2p − 3) (cid:18)p − 2
k − 1 (cid:18)p − 2
j (cid:18)2p − 4
p − 2 (cid:18)2p − 1
p − 1 p p − 1 p(p − 1) p ≡ . ≡ (3 + 8p) ≡ − (5p + 3) (mod p3). 2 3 − 8p 18 18 Suy ra p−1
(cid:88) k ≡ k=0 p p (1 − 3p) − (p − 1)2 (5p + 3) ≡ − p2 k2H 2 6 4
p2 (mod p3).
9 18 Do đó p−1
(cid:88) k ≡ − k=1 4 k2H 2 (mod p). 9 3 iii) Theo bổ đề 2.3.1, ta có k p−1
(cid:88) p−1
(cid:88) k ≡ k=0 k=0 = H 3 (cid:1)
1 − (−1)k(cid:0)p−1
p (cid:80)
p3 (mod p3), ở đó p−1
(cid:88) k=0 (cid:32) (cid:19) (cid:19)2 (cid:19)3(cid:33) (cid:88) := 1 − 3(−1)k + 3 − (−1)3k (cid:18)p − 1
k (cid:18)p − 1
k (cid:18)p − 1
k (cid:19) − (−1)n = p − 3(1 − 1)p−1 + 3 (cid:18)2p − 2
p − 1 (3n)!
(n!)3 (theo bổ đề2.3.5) 39 với n = (p − 1)/2. Lưu ý rằng (cid:19) (cid:19) p p ≡ (mod p4). = (cid:18)2p − 2
p − 1 (cid:18)2p − 1
p − 1 2p − 1 2p − 1 Ngoài ra n
(cid:89) k=1 k(p − k)(p + k) p (−1)n (3n)!
(n!)3 = (−1)n k3 n
(cid:89) k=1 p + n
p2 p p 2p = = (mod p4), 1 − ≡ p + n k2 p + n 3p − 1 1
k2 ≡ Hp−1,2 ≡ 0 (mod p). n
(cid:80)
k=1 vì 2 Kết hợp hai điều trên, ta thu được p−1
(cid:88) k ≡ k=0 p + 3p/(2p − 1) − 2p/(3p − 1) ≡ 6 (mod p). H 3 (cid:80)
p3 ≡ p3 p−1
(cid:88) Suy ra k ≡ 6 (mod p). k=1 H 3 iv) Lấy n = (p − 1)/2 trong (2.30) ta có p−2
(cid:88) k=1 (p − 1)/2 + , (cid:1) Hk = 2(p + 1)2/4 Hp−1
p + 1 (−1)k−1
(cid:0)p−1
k p−2
(cid:88) và do đó k=1 (cid:1) Hk ≡ p − 1
(p + 1)2 (mod p3). (−1)k−1
(cid:0)p−1
k Theo bổ đề 2.3.1 với k = 1, 2, . . . , p − 1 ta có k − Hk,2))3
k − Hk,2)) 2(H 2
2(H 2 (cid:1) ≡ 1 − p3(Hk − p
1 − p(Hk − p (−1)k
(cid:0)p−1
k 2 40 k − Hk,2 k − Hk,2 p p (H 2 (H 2 ≡ 1 + p Hk −
+ p2 Hk − 2 2 k − Hk,2) + p2H 2 k (mod p3). p2 (H 2 ≡ 1 + pHk − 2 p−1
(cid:88) Do đó k=1 (cid:1) Hk 1 − p
(p + 1)2 ≡ p−1
(cid:88) k + Hk,2) k=1 (−1)k
(cid:0)p−1
k
p2 ≡ (H 2 Hk 1 + pHk +
(mod p3). 2 p−1
(cid:88) p−1
(cid:88) Lưu ý rằng k=1 k=1 Hk ≡ 1 − p (mod p3) và HkHk,2 ≡ 0 (mod p) bởi (2.24) và (2.29). Do đó p−1
(cid:88) p−1
(cid:88) k + k (mod p3). k=1 k=1 1 p2 (1 − p) H 2 H 3 ≡ p (p + 1)2 − 1 2 p−1
(cid:88) Do đó, cùng với ii) suy ra k ≡ 2p − 2 (mod p2). k=1 H 2 p−1
(cid:88) p−1
(cid:88) p
(cid:88) Chứng minh hệ quả 2.3.1. Nếu n ∈ Z+ thì k = p−k ≡ − k−1 k=1 k=1 k=1 p−1
(cid:88) kH n (p − k)H n kH n j=1 (mod p), = − (j + 1)H n
j 41 và do đó p−1
(cid:88) p−1
(cid:88) k ≡ − k (mod p). k=0 k=1
Từ iv) và iii) của định lý 2.3.1 lần lượt suy ra đồng dư thứ nhất và thứ hai 1 kH n H n 2 trong hệ quả 2.3.1 . p−1
(cid:88) p−1
(cid:88) Từ ii), iv) và đồng dư thứ nhất trong hệ quả 2.3.1, ta có p−k k = k=1 k=1 p−1
(cid:88) p
(cid:88) (p − k)3H 2 k3H 2 k−1 = − k=1 p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) k=1
p−1
(cid:88) k3H 2 ≡ − (k + 1)3H 2
k k − 3 k − 3 k − k=1 k=1 k=1 k=1
= − k3H 2 k2H 2 kH 2 H 2
k p−1
(cid:88) k − 3 k=1 4 ≡ − k3H 2 − − 3 × 1 − (−1) (mod p). 9 Hệ quả 2.3.1. Cho p > 3 là một số nguyên tố. Khi đó p−1
(cid:88) p−1
(cid:88) p−1
(cid:88) k ≡ 1 (mod p), k ≡ −3 (mod p), k ≡ k=1 k=1 k=1 1 kH 2 kH 3 k3H 2 (mod p). 6 Định nghĩa 2.4.1. Dãy Fibonacci Fn được định nghĩa bởi hệ thức truy hồi sau n ≥ 2, (2.31) Fn = Fn−1 + Fn−2, với các giá trị ban đầu F0 = 0, F1 = 1. Ví dụ 2.4.1. Theo định nghĩa, ta có dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . 42 Từ công thức truy hồi (2.31) , ta có Fn−2 = Fn − Fn−1 để mở rộng các số Fibonacci với chỉ số âm. Ta có F−1 = F1−2 = F1 − F0 = 1 − 0 = 1 F−2 = F0−2 = F0 − F−1 = 0 − 1 = −1 F−3 = F−1 − F−2 = 1 − (−1) = 2 F−4 = F−2 − F−3 = −1 − 2 = −3 F−5 = F−3 − F−4 = 2 − (−3) = 5 . . . Bằng phương pháp quy nạp, ta có F−n = (−1)n+1Fn. Định lí 2.4.1. Với n là số nguyên dương bất kỳ, ta có (2.32) F−n = (−1)n+1Fn. Chứng minh. Thật vậy, với n = 1 ta có f−1 = 1 = (−1)1+1F1. Giả sử, đẳng thức đúng tới n > 1, ta chứng minh đẳng thức đúng với n + 1. Thật vậy, theo giả thiết quy nạp và (2.31), ta có F−(n+1) = F−(n−1) − F−n = (−1)nFn−1 − (−1)n+1Fn = (−1)n+2Fn + (−1)n+2F(n−1) = (−1)n+2(Fn + F(n−1)) = (−1)n+2Fn+1. 43 Tiếp theo là một số hệ thức của dãy Fibonacci. n
(cid:88) Định lí 2.4.2. Với mọi n ≥ 0 ta có i=0 (2.33) Fi = Fn+2 − 1. Chứng minh. Ta có F0 = F2 − F1, F1 = F3 − F2, F2 = F4 − F3, . . . Fn−1 = Fn+1 − Fn, Fn = Fn+2 − Fn+1. Cộng các đẳng thức trên theo từng vế, ta được F0 + F1 + F2 + · · · + Fn = Fn−2 − F1, n
(cid:88) hay i=0 Fi = Fn+2 − 1. n−1
(cid:88) Định lí 2.4.3. a) Tổng các số Fibonacci với chỉ số lẻ i=0 (2.34) F2i+1 = F2n. n
(cid:88) b) Tổng các số Fibonacci với chỉ số chẵn i=0 (2.35) F2i = F2n+1 − 1. 44 Chứng minh. a) Ta có F1 = F2, F3 = F4 − F2, F45 = F6 − F4, . . . F2n−3 = F2n−2 − F2n−4, F2n−1 = F2n − F2n−2. n−1
(cid:88) Cộng các đẳng thức trên theo từng vế, ta được i=0 F2i+1 = F2n. 2n
(cid:88) b) Từ (2.33), ta có đẳng thức i=0 (2.36) Fi = F2n+2 − 1. n
(cid:88) Lấy đẳng thức (2.36) từ đi đẳng thức (2.34) vế với vế, ta được i=0 F2i = F2n+2 − 1 − F2n. n
(cid:88) Theo (2.31), ta được i=0 F2i = F2n+1 − 1. n
(cid:88) Định lí 2.4.4. i=0 (2.37) iFi = nFn+2 − Fn+3 + 2. Chứng minh. Ta có F0 + F1 + F2 + F3 + · · · + Fn−1 + Fn = Fn+2 − 1, 45 F0 + F1 + F2 + F3 + · · · + Fn−1 = Fn+1 − 1, . . . F0 + F1 + F2 = F4 − 1, F0 + F1 = F3 − 1, F0 = F2 − 1. Cộng theo vế các đẳng thức trên, ta được (n+1)F0+nF1+(n−1)F2+· · ·+2Fn−1+Fn = F2+F3+· · ·+Fn+2−(n−1), hay (n+1)F0+nF1+(n−1)F2+· · ·+2Fn−1+Fn = F0+F1+· · ·+Fn+2−(n+2). Theo (2.31) và (2.33), ta được (n + 1)F0 + nF1 + (n − 1)F2 + · · · + 2Fn−1 + Fn = Fn+4 − (n + 3), hay (n + 1)F0 + nF1 + (n − 1)F2 + · · · + 2Fn−1 + Fn = Fn+2 + Fn+3 − (n + 3). Mặt khác, ta có (n + 1)F0 + (n + 1)F1 + (n + 1)F2 + · · · + (n + 1)Fn = (n + 1)Fn+2 − (n + 1). n
(cid:88) Từ đó, suy ra i=0 iFi = (n + 1)Fn+2 − (n + 1) − (F2n+2 + Fn+3 − (n + 3)), n
(cid:88) hay i=0 iFi = nFn+2 − Fn+3 + 2. 46 n
(cid:88) Định lí 2.4.5. Với n > 1, ta có i = FnFn+1. i=0 F 2 (2.38) Chứng minh. Từ (2.31), ta có Fi = Fi+1 − Fi−1. Suy ra i = Fi(Fi+1 − Fi−1) = FiFi+1 − Fi−1Fi. F 2 Do đó, ta có 1 = F1F2, F 2 2 = F2F3 − F1F2, F 2 3 = F3F4 − F2F3, F 2 . . . n−1 = Fn−1Fn − Fn−2Fn−1, F 2 n = FnFn+1 − Fn−1Fn. F 2 n
(cid:88) Cộng vế với vế các đẳng thức trên, ta được i = FnFn+1. i=0 F 2 Định lí 2.4.6 (Đẳng thức Cassini). Với n > 1, ta có n = (−1)n. (2.39) Fn−1Fn+1 − F 2 Chứng minh. Chứng minh bằng quy nạp. Với n = 2, ta có 2 = 1.2 − 1 = 1 = (−1)2. F1F3 − F 2 47 Giả sử, đẳng thức với n > 2, ta chứng minh đẳng thức đúng với n + 1. Thật vậy, theo (2.31) và giả thiết quy nạp, ta có n+1 = Fn(Fn + Fn+1) − (Fn + Fn−1)2 FnFn+2 − F 2 n − 2FnFn−1 − F 2 n−1 n + FnFn+1 − F 2
= FnFn+1 − 2FnFn−1 − F 2 n−1 = F 2 n−1 = Fn(Fn + Fn−1) − 2FnFn−1 − F 2 n − FnFn−1 − F 2 n−1 = F 2 n − Fn−1(Fn−1 + Fn) = F 2 n − Fn−1Fn+1 = F 2 = −(−1)n = (−1)n+1. Suy ra, điều phải chứng minh. Định lí 2.4.7. (2.40) Fn+m = Fn−1Fm + FnFm+1. Chứng minh. Chứng minh bằng quy nạp theo m. Với m = 1, ta có Fn+1 = Fn−1F1 + FnF2 = Fn−1 + Fn. Với m = 2, ta có Fn+2 = Fn−1F2 + FnF3 = 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, theo (2.31) và giả thiết quy nạp, ta có Fn+m+1 = Fn+m−1 + Fn+m = Fn−1Fm−1 + FnFm + Fn−1Fm + FnFm+1 48 = Fn−1(Fm−1 + Fm) + Fn(Fm + Fm+1) = Fn−1Fm+1 + FnFm+2. Định lí 2.4.8 (Đẳng thức d’Ocagne). (2.41) FmFn+1 − Fm+1Fn = (−1)nFm−n. Chứng minh. Theo (2.32) và (2.34), ta có Fm−n = FmF−n−1 + Fm+1F−n = Fm(−1)n+2Fn+1 + Fm+1(−1)n+1Fn = (−1)n(FmFn+1 − Fm+1Fn), hay FmFn+1 − Fm+1Fn = (−1)nFm−n. Định lí 2.4.9. (2.42) F2n = Fn(Fn−1 + Fn+1). Chứng minh. Theo (2.34) với m = n, ta có F2n = Fn−1Fn + FnFn+1 = Fn(Fn−1 + Fn+1). Định lí 2.4.10. n+1. n + F 2 (2.43) F2n+1 = F 2 49 Chứng minh. Chứng minh bằng quy nạp. Với n = 0 ta có 0 + F 2
1 . F1 = 1 = 0 + 1 = F 2 Với n = 1 ta có 1 + F 2
2 . F3 = 2 = 1 + 1 = F 2 Với n = 2 ta có 2 + F 2
3 . F5 = 5 = 1 + 4 = F 2 Giả sử đẳng thức đúng với n > 2. ta chứng minh đẳng thức đúng với n + 1. n+1 + F 2
F 2 Thật vậy, theo (2.31), (2.42) và giả thiết quy nạp, ta có n + 2FnFn+1 + F 2 n+1 = F 2 n+2 = (Fn−1 + Fn)2 + (Fn + Fn+1)2
n−1 + 2Fn−1Fn + F 2
n + F 2
n + 2Fn(Fn−1 + Fn+1) + F 2
n−1 + F 2 n + F 2 n+1 = F 2 = F2n−1 + 2F2n + F2n+1 = F2n+1 + F2n+2 = F2n+3. Suy ra điều phải chứng minh. Định lí 2.4.11. n+1 + 2Fk−1Fn+1Fn + Fk−2F 2
n . (2.44) F2n+k = FkF 2 Chứng minh. Chứng minh bằng quy nạp theo k. Với k = 2. Theo (2.31) và (2.42), ta có n+1 + 2F2−1Fn+1Fn + F2−2F 2 n+1 + 2F1Fn+1Fn + F0F 2
n n = F2F 2
= F 2 n+1 + 2Fn+1Fn F2F 2 = Fn+1(Fn+1 + 2Fn) = Fn+1(Fn+2 + Fn) 50 = F2(n+1) = F2n+2. Giả sử đẳng thức đúng với k > 2, ta chứng minh đẳng thức đúng với k + 1. Thật vậy, theo (2.31) và giả thiết quy nạp, ta có F2n+k+1 = F2n+k−1 + F2n+k n+1 + 2Fk−2Fn+1Fn + Fk−3F 2 n+1 n + FkF 2
+ 2Fk−1Fn+1Fn + Fk−2F 2
n = Fk−1F 2 n+1(Fk−1 + Fk) + 2Fn+1Fn(Fk−2 + Fk−1) + F 2 n (Fk−3 + Fk−2) = F 2 n+1 + 2FkFn+1Fn + Fk−1F 2
n . = Fk+1F 2 Suy ra điều phải chứng minh. Định lí 2.4.12 (Đẳng thức Cassini). n + 3FnFn+1Fn−1 = 5F 3 n + 3(−1)nFn. (2.45) F3n = 2F 3 Chứng minh. Theo (2.44) với k = n và (2.31), ta có n+1 + 2Fn−1Fn+1Fn + Fn−2F 2
n
= Fn(Fn + Fn−1)2 + 2Fn−1FnFn+1 + Fn−2F 2
n F3n = F2n+n = FnF 2 n−1 + 2Fn−1FnFn+1 + Fn−2F 2
n = F 3 n + 2F 2
n + F 2 n Fn−1 + FnF 2
n (Fn − Fn−2) + F 2 n Fn−1 + FnF 2 n−1 + 2Fn−1FnFn+1 + Fn−2F 2
n = F 3 n + Fn−1Fn(Fn + Fn−1) + 2Fn−1FnFn+1 = 2F 3 n + Fn−1FnFn+1 + 2Fn−1FnFn+1 = 2F 3 n + 3Fn−1FnFn+1. = 2F 3 n − Fn−1Fn+1 = (−1)n−1,
F 2 Theo (2.39), ta có hay n + (−1)n−1. Fn−1Fn+1 = F 2 51 Vậy n + 3FnFn+1Fn−1 = 5F 3 n + 3(−1)nFn. F3n = 2F 3 Phần cuối chúng ta trình bày ứng dụng của số Fibonacci và Stirling để giải các bài toán tổ hợp, bài toán thi Olympic và thi học sinh giỏi. Như ta đã biết, các số Fibonacci có ứng dụng rất rộng và một trong những ứng dụng đó là dùng để giải một số bài toán tổ hợp, bài toán thi Olympic và thi học sinh giỏi. Bài 1 (Ireland National Olympiad 1999). Chứng minh rằng với mỗi số n nguyên dương bất kì, luôn tồn tại vô hạn các số Fibonacci chia hết cho n.
Giải. Ta xét các cặp (Fi, Fi+1) theo mod n với i ∈ N. Do có vô số cặp như
vậy nhưng chỉ có n2 cặp theo mod n, nên theo nguyên lý Dirichlet, tồn tại hai cặp (Fi, Fi+1) và (Fi+m, Fi+m+1), m > 0 sao cho: Fi ≡ Fi+m(mod n) Fi+1 ≡ Fi+m+1(mod n) ⇒ Fi−1 ≡ Fi+m−1(mod n). Lặp lại quá trình trên với mọi j ∈ N ta có Fj ≡ Fj+m(mod n). Vậy với mọi số nguyên dương k thì F0 ≡ Fkm ≡ 0(mod n). 52 Ta có điều cần chứng minh. Bài 2. Chứng minh rằng với mỗi số tự nhiên n với n ≥ 6 thì giữa Fn và Fn+1 luôn tồn tại một số chính phương. Giải. Ta sẽ chứng minh (cid:112) (cid:112)Fn+1 − Fn > 1, ∀n ≥ 6. - Với trường hợp 6 ≤ n ≤ 7 bằng cách thử trực tiếp ta thấy bài toán đúng trong trường hợp này. - Trường hợp n ≥ 8, bất đẳng thức cần chứng minh tương đương với Fn−1 (cid:112) √ √ > 1 (cid:112)Fn + Fn−1 − Fn = Fn + Fn−1 + Fn (cid:112) Fn. ⇔Fn−1 > (cid:112)Fn + Fn−1 + Ta có Fn = Fn−1 + Fn−2 < 2Fn−1. Do đó (cid:112) Fn < (cid:112)3Fn−1 + (cid:112)2Fn−1. √ √ (cid:112)Fn + Fn−1 +
√ √ 2. Vậy bất đẳng thức được chứng minh. Do Lại có Fn−1 ≥ F7 > √ 3 +
√ bất đẳng thức trên nên giữa Fn+1 và Fn tồn tại một số nguyên tức giữa Fn+1 và Fn tồn tại một số chính phương. Bài 3 (Đề chọn đội tuyển Đà Nẵng 2009-2010). Cho dãy (an) thỏa mãn: a0 = 1, a1 = 1, an+2 = 7an+1 − an − 2, ∀n ∈ N. Chứng minh rằng an là một số chính phương với mọi n ∈ N.
Giải. Chứng minh bằng quy nạp ta có an = (F2n−1)2. Từ đó, ta có điều cần chứng minh. Bài 4. Đếm tất cả số cách xếp n quân Domino kích thước 2 × 1 phủ kín bảng có kích thước 2 × n. Giải. Đặt S(n) là số cách phủ thỏa yêu cầu bài toán. Xét cấu hình các ô 53 n − 1 n 1 2 3 4 . . . 2n − 1 2n n + 1 n + 2 n + 3 n + 4 . . . Nếu 1 quân Domino phủ lên cặp ô (n, 2n) thì phần còn lại là 1 bảng 2×(n−1) nên có S(n − 1). Nếu 1 quân Domino phủ lên cặp ô (n − 1, n) hoặc (2n − 1, 2n) thì ta bắt buộc phải phủ lên cặp ô còn lại (nếu Domino đầu tiên phủ lên (n − 1, n) thì các thứ 2 phải phủ lên (2n − 1, 2n) và ngược lại), khi đó phần còn lại là 1 bảng 2 × n − 2 nên có S(n − 2) cách chọn. Ta có công thức tổng quát S(n) = S(n − 1) + S(n − 2) với S(1) = 1, S(2) = 2. Dễ thấy đây là dãy Fibonacci. Bài 5 (Bulgaria National Olympiad 1997). Cho tập Sn = {1, 2, . . . , n}, hỏi có bao nhiêu tập khác rỗng Sαn ⊂ Sn thỏa mãn Sαn không chứa bất kì hai số tự nhiên liên tiếp nào? Giải. Gọi An là số tập khác rỗng Sαn ⊂ Sn thỏa mãn Sαn không chứa bất kì hai số tự nhiên liên tiếp nào. Ta sẽ chứng minh An+2 = An+1 + An. Ta có: - Số tập Sαn+2 không chứa phần tử n + 2 sẽ bằng số tập Sαn+1. - Số tập Sαn+2 chứa phần tử n + 2 sẽ bằng số tập Sαn (do những tập đó không chứa n + 1). Theo quy tắc cộng ta có An+2 = An+1 + An. Lại có A1 = 1, A2 = 2. Từ đó ta có An = Fn, ∀n ∈ N∗. Bài 1. Tìm số cách đặt n vật phân biệt vào m hộp phân biệt, nếu kể đến thứ tự từ trái qua phải của các vật trong hộp biết rằng có thể cho phép một số hộp 54 để trống (chú ý rằng nếu m > n, ít nhất m − n hộp phải bỏ trống). Giải. Giả sử số cần tìm là f (n, m). Giả thiết rằng đã có f (n − 1, m) và một sự phân phối n − 1 vật đó là : mang i1 vật vào hộp 1, i2 vật vào hộp 2,..., im vật vào hộp m, trong đó ik ≥ 0, k = 1, 2, . . . , m và i1 + i2 + · · · + im = n − 1. Vật thứ n có thể vào hộp k (k = 1, 2, . . . , m) theo ik + 1 cách (vị trí đầu tiên về bên trái, vị trí thứ 2 từ trái qua phải, ..., vị trí thứ ik + 1 tính từ trái qua phải). Do đó có (i1 + 1) + (i2 + 1) + ... + (im + 1) = n − 1 + m cách xếp cho vật thứ n. Vậy ta có quan hệ f (n, m) = (n − 1 + m)f (n − 1, m) = (n + m − 1)(n + m − 2)...m. Bài 2. Có bao nhiêu cách để làm nhiều bộ khác nhau của k chiếc vòng đeo tay từ n hạt riêng biệt. Biết rằng một vòng đeo tay cần phải có ít nhất một hạt?. Giải. Mỗi cách làm một bộ gồm k chiếc vòng đeo tay từ n hạt riêng biệt tương ứng với một cách phân hoạch tập n phần tử thành k chu trình và mỗi chu trình n có ít nhất một vật. Vậy ta có cách. k Bài 3. Có bao nhiêu cách xếp n nam và m nữ ngồi vào k bàn tròn giống hệt nhau mà mỗi bàn có ít nhất một nam và một nữ. Giải. Ta chia công việc thành hai công đoạn. Sắp xếp nnam vào k bàn tròn sao cho mỗi bàn có ít nhất một người, ta có n
cách. Sắp xếp n nữ vào k k m bàn tròn sao cho mỗi bàn có ít nhất một người, ta có cách. Vậy theo k m nguyên lý nhân ta có số cách sắp xếp là : n
. cách. k k 55 Bài 4. Một thương hiệu nhất định của một sản phẩm cung cấp một trong k (k > 1)giải thưởng cho mỗi sản phẩm của họ với xác xuất bằng nhau cho mỗi sản phẩm. Xác suất có ít nhất một giải thưởng khi họ bán ra n sản phẩm là bao nhiêu?
Giải. Tổng số khả năng các giải thưởng là kn. Khả năng để có ít nhất mỗi giải thưởng tương ứng với một cách phân hoạch tập n phần tử thành k khối mà n
n
mỗi khối phải có ít nhất một vật là . Vậy xác suất là k
kn . k
Bài 5. Đếm số cách phân phối n vật phân biệt vào m hộp nếu thỏa mãn: a) m hộp giống nhau và mỗi hộp phải có ít nhất một vật. b) m hộp giống nhau và cho phép có hộp trống. c) Các hộp đều phân biệt và mỗi hộp phải có ít nhất một vật. Giải. a) Mỗi cách phân phối n vật phân biệt vào m hộp thỏa mãn m hộp giống nhau và mỗi hộp phải có ít nhất một vật tương ứng với một cách phân hoạch
n
cách . tập n phần tử thành m khối. Vậy có m n n n
b) Vì cho phép có hộp trống nên ta có m cách phân hoạch: 1 hộp trống có
cách. Vậy cách, ..., m hộp trống có cách, 2 hộp trống có m n n n 1
2
+ + . . . có cách. c) Các hộp phân biệt nên có m! hoán vị 1 2 m n
của m hộp. Vậy có m!. cách . 2 n m
= (cid:0)n (cid:1). Bài 6. Chứng minh rằng n − 1 Giải. Dễ thấy đẳng thức này đúng vì việc phân chia một tập n phần tử thành n − 1 tập con chính là việc phân chia tập đó thành một tập có 2 hai phần tử 56 và n − 2 tập con khác. Vì vậy, số cách phân chia chính là số cách chọn 2 phần tử trong số n phần tử . 57 Ví dụ và bài tập tương tự Bài 1. Cho dãy số (un) được xác định bởi u0 = 0, u1 = 1 = (−1)n
un+1 − 3un + un−1
2 với mọi số nguyên dương n. Chứng minh rằng un là số chính phương với mọi n ≥ 0. Bài 2. Cho dãy số (un) được xác định bởi
u1 = u2 = 1, u3 = 4 un+3 = 2un+2 + 2un+1 − un với mọi số nguyên dương n. Chứng minh rằng un là số chính phương với mọi n ≥ 1. Bài 3. Cho dãy số (un) được xác định bởi
u1 = 1, u2 = 1 un+2 = 7un+1 − un − 2 với mọi n ≥ 1. Chứng minh rằng un là số chính phương với mọi n ≥ 1.
Bài 4. (IMO 1981) Tìm giá trị nhỏ nhất của P = m2 + n2, trong đó m, n là
các số thỏa mãn: 1 ≤ m; n ≤ 1981 và (n2 − mn − m2)2 = 1. Bài 5. Chứng minh rằng tồn tại vô hạn số hạng của dãy Fibonacci chia hết 2012. Bài 6. Cho dãy số (un) được xác định bởi
u1 = 0, u2 = 1 un+2 = un + un+1 + 1 với mọi n ≥ 0. Chứng minh rằng với p là số nguyên tố thì up(up+1 + 1) chia hết cho p. 58 Trong luận văn tôi đã trình bày được các kết quả sau: (1) Trình bày khái niệm, ví dụ và một số kết quả của các số Stirling, số Euler, số Harmonic và số Fibonacci. (2) Nêu ứng dụng của số Stirling và Fibonacci trong toán học phổ thông. 59 [1] Nguyễn Thu Trang (2014), Số Fibonacci, dãy Lucas, Luận văn Thạc sĩ Toán học, Trường Đại học Khoa học - Đại học Thái Nguyên. [2] Đặng Thị Nguyễn Việt (2012), Số Stirling và ứng dụng, Luận văn Thạc sĩ Toán học, Trường Đại học Đà Nẵng. [3] Nguyễn Xuân Trọng (2013), Ứng dụng số Stirling vào giải toán tổ hợp, Luận văn Thạc sĩ Toán học, Trường Đại học Đà Nẵng. [4] Zhi-Wei Sun (2011), Arithmetic theory of harmonic numbers, Proceed- ing of the American Mathematican Society, volume 140, number 2, February 2012, pages 415-428. [5] Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994), Concrete Mathematics, Second Edition, Wesley. [6] Peter J. Cameron and Dima G.Fon-Der-Flaass, Fibonacci notes.2.4 Số Fibonacci
2.5 Ứng dụng trong toán phổ thông
2.5.1 Ứng dụng của số Fibonacci
2.5.2 Ứng dụng của số Stirling
Kết luận
Tài liệu tham khảo
Tiếng Việt
Tiếng Anh
