Trả lời nhanh
Chứng minh cn0 + cn1 + … + cnn = 2^n. Với mọi n ∈ ℕ*, ta có Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn = 2n. Cách chứng minh ngắn nhất: theo công thức nhị thức Newton, (a + b)n = Cn0an + Cn1an−1b + … + Cnnbn. Thay a = b = 1, vế trái bằng (1 + 1)n = 2n, vế phải bằng đúng tổng cần tính. Ngoài ra có thể chứng minh bằng cách đếm số tập con hoặc bằng quy nạp toán học.
Đề bài và ý tưởng chứng minh
Đề bài: Cho n ∈ ℕ*. Chứng minh rằng Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn = 2n.
Tổng ở vế trái là tổng tất cả các số tổ hợp chập k của n phần tử, với k chạy từ 0 đến n. Đẳng thức này là một trong những hệ quả quan trọng nhất của nhị thức Newton, thường gặp trong chuyên đề nhị thức Newton lớp 10 và trong các bài toán đếm. Bài viết trình bày ba cách chứng minh, mỗi cách cho em một góc nhìn khác:
- Cách 1 dùng đại số: khai triển nhị thức Newton.
- Cách 2 dùng tổ hợp: đếm số tập con của một tập hợp theo hai cách.
- Cách 3 dùng quy nạp toán học và hằng đẳng thức Pascal.
Kiến thức cần nhớ
- Số tổ hợp chập k của n phần tử (0 ≤ k ≤ n): Cnk = n! / (k!(n − k)!), quy ước 0! = 1 nên Cn0 = Cnn = 1.
- Tính chất đối xứng: Cnk = Cnn−k.
- Hằng đẳng thức Pascal: Cnk−1 + Cnk = Cn+1k với 1 ≤ k ≤ n.
- Công thức nhị thức Newton: (a + b)n = Cn0an + Cn1an−1b + Cn2an−2b2 + … + Cnn−1abn−1 + Cnnbn.
Cách 1: Dùng khai triển nhị thức Newton
Áp dụng công thức nhị thức Newton với a = 1 và b = 1. Khi đó mọi lũy thừa an−kbk đều bằng 1, nên:
(1 + 1)n = Cn0 · 1 + Cn1 · 1 + … + Cnn · 1.
Vế trái bằng 2n, vế phải chính là Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn. Vậy đẳng thức được chứng minh.
Đây là cách được dùng nhiều nhất trong bài thi vì chỉ cần hai dòng. Ý tưởng “chọn giá trị đặc biệt cho a, b” còn giúp em tính được nhiều tổng khác, xem phần mở rộng bên dưới.
Cách 2: Đếm số tập con theo hai cách
Xét tập hợp A = {1; 2; …; n} có n phần tử. Ta đếm số tập con của A.
Đếm theo số phần tử. Số tập con có đúng k phần tử là số cách chọn k phần tử từ n phần tử, tức Cnk. Cho k chạy từ 0 (tập rỗng) đến n (chính tập A), tổng số tập con là Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn.
Đếm theo từng phần tử. Để tạo một tập con, với mỗi phần tử của A ta có đúng 2 lựa chọn: lấy hoặc không lấy. Theo quy tắc nhân, có 2 · 2 · … · 2 (n thừa số) = 2n tập con.
Hai cách đếm cùng một đại lượng nên kết quả phải bằng nhau, suy ra Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn = 2n.
Ví dụ với n = 3, tập {1; 2; 3} có 1 tập rỗng, 3 tập một phần tử, 3 tập hai phần tử và 1 tập ba phần tử: 1 + 3 + 3 + 1 = 8 = 23.
Cách 3: Chứng minh bằng quy nạp toán học
Đặt Sn = Cn0 + Cn1 + Cn2 + … + Cnn−1 + Cnn. Ta chứng minh Sn = 2n với mọi n ≥ 1.
Bước 1 (n = 1): S1 = C10 + C11 = 1 + 1 = 2 = 21. Đẳng thức đúng.
Bước 2: Giả sử đẳng thức đúng với n = m (m ≥ 1), tức Sm = 2m. Ta chứng minh Sm+1 = 2m+1.
Viết Sm+1 = Cm+10 + [Cm+11 + Cm+12 + … + Cm+1m] + Cm+1m+1. Dùng hằng đẳng thức Pascal cho các số trong ngoặc vuông: Cm+1k = Cmk−1 + Cmk với 1 ≤ k ≤ m. Đồng thời Cm+10 = Cm0 = 1 và Cm+1m+1 = Cmm = 1. Gom lại thành hai nhóm:
- Nhóm thứ nhất: Cm0 + Cm1 + … + Cmm = Sm (gồm Cm+10 và các số Cmk).
- Nhóm thứ hai: Cm0 + Cm1 + … + Cmm = Sm (gồm các số Cmk−1 và Cm+1m+1).
Do đó Sm+1 = 2Sm = 2 · 2m = 2m+1. Theo nguyên lí quy nạp, đẳng thức đúng với mọi n ∈ ℕ*.
Cách này cũng giải thích vì sao trong tam giác Pascal, tổng mỗi dòng gấp đôi tổng dòng trước: mỗi số của dòng trên được “dùng” hai lần để tạo dòng dưới.
Kiểm tra với các giá trị n nhỏ
| n | Các số Cnk | Tổng | 2n |
|---|---|---|---|
| 1 | 1, 1 | 2 | 2 |
| 2 | 1, 2, 1 | 4 | 4 |
| 3 | 1, 3, 3, 1 | 8 | 8 |
| 4 | 1, 4, 6, 4, 1 | 16 | 16 |
| 5 | 1, 5, 10, 10, 5, 1 | 32 | 32 |
Hệ quả và bài tập mở rộng có đáp án
Bài 1. Chứng minh Cn0 − Cn1 + Cn2 − … + (−1)nCnn = 0 với n ≥ 1.
Đáp án: Thay a = 1, b = −1 vào nhị thức Newton: (1 − 1)n = 0 bằng đúng tổng đan dấu.
Bài 2. Chứng minh Cn0 + Cn2 + Cn4 + … = Cn1 + Cn3 + Cn5 + … = 2n−1.
Đáp án: Gọi P là tổng các số có chỉ số chẵn, Q là tổng các số có chỉ số lẻ. Theo đề bài gốc P + Q = 2n, theo bài 1 P − Q = 0. Suy ra P = Q = 2n−1.
Bài 3. Tính T = Cn0 + 2Cn1 + 22Cn2 + … + 2nCnn.
Đáp án: Thay a = 1, b = 2: T = (1 + 2)n = 3n.
Bài 4. Tìm n biết Cn0 + Cn1 + … + Cnn = 1024.
Đáp án: 2n = 1024 = 210 nên n = 10.
Bài 5. Một lớp có 6 câu lạc bộ. Mỗi học sinh có thể đăng kí tham gia một số câu lạc bộ, nhưng ít nhất là một. Hỏi có bao nhiêu cách đăng kí?
Đáp án: Số tập con khác rỗng của tập 6 phần tử là C61 + … + C66 = 26 − 1 = 63 cách.
Những lỗi thường gặp
- Quên số hạng Cn0: tổng từ Cn1 đến Cnn chỉ bằng 2n − 1.
- Thay sai giá trị: chọn a = 1, b = 0 sẽ chỉ còn lại Cn0 = 1, không ra tổng cần tìm.
- Quy nạp thiếu bước kiểm tra n = 1 hoặc dùng hằng đẳng thức Pascal cho cả k = 0 và k = m + 1, khi đó Cm−1 và Cmm+1 không xác định theo định nghĩa. Hai số hạng đầu, cuối cần tách riêng như lời giải trên.
Câu hỏi thường gặp
Tổng các hệ số trong khai triển (a + b)ⁿ bằng bao nhiêu?
Bằng 2ⁿ. Thay a = b = 1 vào khai triển ta được tổng các hệ số Cn0 + Cn1 + … + Cnn = (1 + 1)ⁿ = 2ⁿ.
Một tập hợp có n phần tử có bao nhiêu tập con?
Có 2ⁿ tập con, kể cả tập rỗng và chính nó. Nếu không tính tập rỗng thì có 2ⁿ − 1 tập con.
Tổng Cn1 + Cn2 + … + Cnn bằng bao nhiêu?
Bằng 2ⁿ − 1, vì thiếu số hạng Cn0 = 1 so với tổng đầy đủ 2ⁿ.
Tổng các số Cnk có chỉ số chẵn bằng bao nhiêu?
Bằng 2ⁿ⁻¹ với n ≥ 1, và bằng tổng các số có chỉ số lẻ.