Dtth part4 booklet là tài liệu môn Toán trong chương trình Lớp 11 được cungthi.online tổng hợp và biên soạn từ các nguồn chia sẻ trên Internet. Tạo nguồn tài liệu giúp các bạn trong việc ôn luyện và học tập
Những địa chỉ uy tín để bạn mua sách
Nội dung tóm tắt
136 5.3. Các bài toán
Ta có
1
p
(
p
i
)
=
p!
p(p− i)!i!
=
(p− i+ 1)(p− i+ 2)...(p− 1)
i!
≡ (−1)
i−1(i− 1)!
i
≡ (−1)
i−1
i
(mod p)
⇒ S ≡ 1− 1
2
+
1
3
− ...+ (−1)
k−1
k
(mod p)
Trường hợp 1: p = 3h+ 1 thì
k =
⌊
2p
3
⌋
=
⌊
2(3h+ 1)
3
⌋
=
⌊
2h+
2
3
⌋
= 2h
⇒ p− k − 1 = h⇒ p− h = k + 1
Khi đó
S ≡ 1 + 1
2
+
1
3
+ ...+
1
k
− 2
(
1
2
+
1
4
+ ...+
1
k
)
≡ 1 + 1
2
+
1
3
+ ...+
1
k
−
(
1
1
+
1
2
+ ...+
1
h
)
(mod p)
Ta có −1
h
≡ 1
p− h
(mod p) nên
S ≡ 1 + 1
2
+
1
3
+ ...+
1
k
+
1
k + 1
+ ...
1
p− 1
(mod p)
Trường hợp 2: p = 3h+ 2 thì
k =
⌊
2p
3
⌋
=
⌊
2(3h+ 2)
3
⌋
=
⌊
2h+ 1 +
1
3
⌋
= 2h+ 1⇒ p− h = k + 1
Khi đó
S ≡ 1 + 1
2
+
1
3
+ ...+
1
k
− 2
(
1
2
+
1
4
+ ...+
1
k − 1
)
≡ 1 + 1
2
+
1
3
+ ...+
1
k
−
(
1
1
+
1
2
+ ...+
1
h
)
(mod p)
Ta có −1
h
≡ 1
p− h
(mod p) nên
S ≡ 1 + 1
2
+
1
3
+ ...+
1
k
+
1
k + 1
+ ...
1
p− 1
(mod p)
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
4.5. Bài tập minh họa 101
Lời giải.
Ta có :
n∑
k=0
(
4n
2n− 2k
)(
k + n
n
)
=
n∑
k=0
(
4n
2n+ 2k
)(
k + n
k
)
A
=
[
t4n
] t2n
(1− t)2n+1
[
1
(1− u)n+1
∣∣∣∣u = t2(1− t)2
]
=
[
t2n
] 1
(1− t)2n+1
[
1
(1− u)n+1
∣∣∣∣u = t2(1− t)2
]
=
[
t2n
] 1
(1− t)2n+1
· (1− t)
2n+2
(1− 2t)n+1
=
[
t2n
] 1− t
(1− 2t)n+1
=
[
t2n
] 1
(1− 2t)n+1
−
[
t2n−1
] 1
(1− 2t)n+1
= 22n
(
n+ 1 + 2n− 1
2n
)
− 22n−1
(
2n− 1 + n+ 1− 1
2n− 1
)
= 4n
(
3n
n
)
− 4n · 1
2
(
3n− 1
n
)
= 4n
(
3n
n
)
− 4n · 1
2
· 2
3
(
3n
n
)
= 4n · 2
3
(
3n
n
)
Nên từ đây suy ra điều phải chứng minh.
Ví dụ 4.20. Cho bộ ba số nguyên (m,n, r) thỏa mãn 0 ≤ r ≤ n ≤ m−2.
Ký hiệu :P (m; n; r) =
r∑
k=0
(−1)k
(
m+ n− 2 (k + 1)
n
)(
r
k
)
.
Chứng minh rằng:
n∑
r=0
P (m; n; r) =
(
m+ n
n
)
4
Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học
102 4.5. Bài tập minh họa
Nhận xét. Bài Toán này là một trong những bài tác giả thích nhất, vì
nó rất đúng với dụng ý về hàm sinh của tác giả khi viết chuyên đề. Rõ
ràng các cách khác như, đếm 2 cách, quy nạp, ... gần như không hiệu
quả khi ngoại hình bài toán quá cồng kềnh, rối rắm.
Lời giải.
Ta có:
P (m; n; r) =
r∑
k=0
(−1)k
(
m+ n− 2 (k + 1)
n
)(
r
k
)
A
=
[
tn+m−2
] tn
(1− t)n+1
[
(1− u)r|u = t2
]
=
[
tm−2
] (1− t2)r
(1− t)n+1
⇒
n∑
r=0
P (m; n; r) =
n∑
r=0
[
tm−2
] (1− t2)r
(1− t)n+1
=
[
tm−2
] n∑r=0 (1− t2)r
(1− t)n+1
=
[
tm−2
] 1−
(
1− t2
)n+1
1− (1− t2)
(1− t)n+1
=
[
tm−2
] 1− (1− t2)n+1
t2(1− t)n+1
= [tm]
1−
(
1− t2
)n+1
(1− t)n+1
= [tm]
(
1
(1− t)n+1
− (1 + t)n+1
)
= [tm]
1
(1− t)n+1
=
(
m+ n+ 1− 1
m
)
=
(
m+ n
m
)
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
5.3. Các bài toán 135
Lời giải.
Ta có 2 bổ đề:
∀j = 1, p− 1 :
(
p
j
)
... p(
p+ j
j
)
− 1
...p
Và định lý Wolstenholme:
(
2p
p
)
≡ 2 (mod p2) (đã chứng minh ở bài
5.1)
Áp dụng vào bài toán:
p∑
j=0
(
p
j
)(
p+ j
j
)
− 2p − 1
= 1− 1 +
(
2p
p
)
+
p−1∑
j=1
(
p
j
)(
p+ j
j
)
− (1 + 1)p
=
(
2p
p
)
− 2 +
p−1∑
j=1
(
p
j
)((
p+ j
j
)
− 1
)
... p2
Ví dụ 5.13. Cho p là số nguyên tố lớn hơn 3 và k =
⌊
2p
3
⌋
.
Chứng minh rằng:
k∑
i=1
(
p
i
)
...p2
4
Lời giải.
Dễ thấy
(
p
i
)
... p, ∀i = 1, p− 1
Để chứng minh
(
p
1
)
+
(
p
2
)
+ ...+
(
p
k
)
...p2 ta chỉ cần chứng minh
S =
k∑
i=1
1
p
(
p
i
)
...p (5.3)
Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học
134 5.3. Các bài toán
và chia cho số (p−1)! nguyên tố cùng nhau với p, ta biến đổi (5.1) dưới
dạng
N
∏
p!
≡ N
p
(mod p) (5.2)
trong đó
N
∏
p!
là số nguyên bằng
(
n
p
)
.
Vậy ta đã chứng minh xong điều kiện khẳng định đầu tiên của bài toán.
Nếu số
N
p
=
⌊
n
p
⌋
chia hết cho ps thì (5.1),(5.2) vẫn đúng theo module
ps+1.
Suy ra
N
∏
p
=
(
n
p
)
... ps. Vậy khẳng định thứ hai được chứng minh.
Ví dụ 5.11 (Trường Đông toán học miền Nam 2012-2013). Cho số
nguyên tố p. Chứng minh rằng
p∑
i=1
(
p
i
)(
p+ i
i
)
≡ 2p (mod p2)
4
Lời giải.(
p
i
)
≡ 0 (mod p);
(
p+ i
i
)
≡ 1 (mod p)∀i = 1, p− 1
Ta có: (
p
i
)((
p+ i
i
)
− 1
)
... p2
⇒
(
p
i
)(
p+ i
i
)
≡
(
p
i
)
(mod p2)
Suy ra:
p∑
i=0
(
p
i
)(
p+ i
i
)
≡
p∑
i=0
(
p
i
)
≡ 2p (mod p2)
Ví dụ 5.12. Cho p ∈ P và p 6= 2. Chứng minh rằng:
p∑
j=0
(
p
j
)(
p+ j
j
)
≡ 2p + 1 (mod p2)
4
Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp
4.5. Bài tập minh họa 103
Do n+ 1 ≤ m− 1 < m⇒ [tm] (1 + t)n+1 = 0.
Nên từ đây suy ra điều phải chứng minh.
Ví dụ 4.21 (Hoàng Xuân Thanh). Chứng minh rằng với mọi số nguyên
dương n, ta có:
n∑
k=0
(−2)k
(
n+ k
2k
)
= (−1)b
n+1
2 c
4
Nhận xét. Tất nhiên là so với những bài toán nêu ở trên, bài này chỉ là
bài dễ. Tuy nhiên, dụng ý tác giả đưa ra bài này là một mục đích khác,
tức là: Trong trình bày lời giải, đôi khi ta không muốn phải chứng minh
lại các định lý A (4.2); B (4.3), khi đó, ta sẽ ngầm dùng chúng và sử
dụng luôn kết quả hàm sinh tìm được để lời giải ngắn gọn. Và cũng là
để làm “vừa ý” những người đọc vốn không quen với kiểu trình bày có
các ẩn u.
Chẳng hạn với bài toán này: khi dùng định lý A (4.2), ta tìm ra được
ngay hàm sinh cần tìm: f (t) =
1− t
1 + t2
, và hệ số cần xét là tn.
Lời giải. Bây giờ, tuỳ theo số dư của n trong phép chia cho 4, ta có:
(−1)b
n+1
2 c = [tn] 1
1 + t2
− [tn] t
1 + t2
= [tn]
1− t
1 + t2
= [tn]
1
1− t
· (1− t)
2
1 + t2
= [tn]
1
1− t
· 1
1 +
2t
(1− t)2
(Biến đổi này thực ra cũng là từ định lý A (4.2))
