🔙 Quay lại trang tải sách pdf ebook Chuyên đề Đẳng thức Tổ hợp Ebooks Nhóm Zalo Chuyên đề Diễn đàn Toán học Chuyên đề ĐẲNG THỨC TỔ HỢP Vol.1 Chế bản Hoàng Xuân Thanh [hxthanh] Trần Quốc Nhật Hân [perfectstrong] Trần Trung Kiên [Ispectorgadget] Nguyễn Bảo Phúc [dark templar] c 2013 Diễn đàn Toán học Lời giới thiệu Bạn đọc thân mến! Đại Số Tổ Hợp ngày nay đã trở thành một môn học không thể thiếu trong chương trình trung học phổ thông. Khi nói về các bài toán Tổ hợp, chúng ta không thể không nhắc tới một dạng toán rất hay và quen thuộc đó là: Đẳng thức tổ hợp. Đẳng thức tổ hợp (ĐTTH) là những đẳng thức có chứa các hệ số nhị thức thường được phát biểu dưới dạng tính tổng. Có thể nói ĐTTH là một trong những đề tài khó nhất và hấp dẫn nhất của Đại Số Tổ Hợp. Việc ĐTTH xuất hiện thường xuyên trong các kỳ thi Đại Học, học sinh giỏi những năm gần đây, cũng là một dấu hiệu cho thấy sự quan tâm và đầu tư một cách tích cực hơn về vấn đề này. Nhân sự kiện đón xuân Quý Tỵ và kỷ niệm tròn một năm Diễn đàn Toán học khai trương trang chủ mới (16/01/2012 - 16/01/2013), nhóm biên tập chúng tôi cùng nhiều thành viên tích cực của diễn đàn đã chung tay biên soạn một chuyên đề gửi đến bạn đọc. Với một số phương pháp từ cơ bản đến nâng cao về Đại Số Tổ Hợp nói chung và ĐTTH nói riêng, chúng tôi, những người thực hiện chuyên đề này, mong muốn đem đến cho bạn đọc một chút gì đó mới mẻ trong các bài toán về ĐTTH, chẳng hạn như phương pháp Sai Phân, Sai phân từng phần, v.v... Bạn đọc sẽ tìm thấy trong chuyên đề này một số dạng bài toán quen thuộc được nhìn nhận và tiếp cận theo phong cách hoàn toàn mới, qua những ví dụ và bài tập điển hình. i ii Chuyên đề là tập hợp các bài viết của các tác giả: Trần Quốc Nhật Hân (perfectstrong), Bùi Đức Lộc (supermember), Hoàng Xuân Thanh (hxthanh), Lê Kim Nhã (gogo123), Nguyễn Bảo Phúc (Dark Templar), Trần Trung Kiên (Ispectorgadget), Lưu Giang Nam (namheo1996), Hoàng Minh Quân (batigoal), Nguyễn Hiền Trang (tranghieu95) ... cùng sự góp sức của nhiều thành viên tích cực khác trên Diễn đàn Toán học như thầy Châu Ngọc Hùng (hungchng), Lê Hữu Điền Khuê (Nesbit), Đinh Ngọc Thạch (T*genie*), HeilHittler, trungpbc, ... Chuyên đề gồm 6 chương. Chương 1 tóm tắt Tổng quan về hệ số nhị thức. Phương pháp cân bằng hệ số của khai triển nhị thức quen thuộc sẽ được nghiên cứu ở chương 2. Tính tổng bằng Sai Phân và Sai Phân Từng Phần chiếm vị trí ở chương 3. Chương 4 viết về Hàm Sinh và những ứng dụng mạnh mẽ trong chứng minh ĐTTH. Chương 5 là Một số ứng dụng của nhị thức trong các bài toán Số Học. Khép lại chuyên đề là chương 6 Phương pháp đếm bằng hai cách. Những phương pháp và bài tập được giới thiệu trong chuyên đề này có thể chưa phải là hay nhất, chưa phải là tổng quát nhất. Nhưng hy vọng bạn đọc hãy tiếp tục nghiên cứu, sáng tạo. Đó mới là tinh thần học toán mà chuyên đề muốn mang tới. Tài liệu này cũng thay cho lời chúc mừng năm mới của Diễn đàn Toán học gửi đến quý bạn đọc! Do thời gian chuẩn bị gấp rút, một số nội dung chưa được đầu tư một cách tỉ mỉ và không thể tránh khỏi sai sót, chúng tôi mong bạn đọc thông cảm. Mọi sự ủng hộ, đóng góp, phê bình của độc giả sẽ là nguồn động viên tinh thần to lớn cho ban biên tập cũng như các tác giả để những phiên bản cập nhật sau của chuyên đề được tốt hơn. Mọi trao đổi góp ý xin gửi về địa chỉ email : [email protected]. Trân trọng! Nhóm biên tập Chuyên đề Đẳng Thức Tổ Hợp. Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp Mục lục iLời giới thiệu Chương 1 1 11 41 Tổng quan về hệ số nhị thức 1.1 Một số khái niệm 1 1.2 Các tính chất cơ bản 4 Chương 2 Phương pháp cân bằng hệ số chứng minh đẳng thức tổ hợp 2.1 Khai triển số thực 12 2.2 Ứng dụng số phức 22 Chương 3 Tính tổng, chứng minh ĐTTH bằng phương pháp Sai phân từng phần 3.1 Sai Phân (Difference) 42 iii iv Mục lục 3.2 Sai Phân Từng Phần 43 3.3 Một số bài toán và Ví dụ minh hoạ 44 3.4 Bài tập tự luyện 68 Chương 4 71 Sử dụng hàm sinh chứng minh đẳng thức tổ hợp 4.1 Thay lời mở đầu 72 4.2 Những biến đổi đại số thường gặp với n k 74 125 151 4.3 Những dạng khai triển hàm sinh cần biết 75 4.4 Những định lý cơ bản trong tính tổng dùng hàm sinh 76 4.5 Bài tập minh họa 81 4.6 Các bài toán không mẫu mực 108 4.7 Bài tập tự luyện 121 Chương 5 Ứng dụng đẳng thức tổ hợp vào Số học 5.1 Định lý 125 5.2 Một số hệ thức cơ bản 126 5.3 Các bài toán 127 5.4 Bài tập 148 Chương 6 Kỹ thuật đếm bằng hai cách chứng minh đẳng thức tổ hợp 6.1 Nguyên lí đếm bằng hai cách 152 6.2 Ứng dụng chứng minh đẳng thức tổ hợp 153 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp Mục lục v 6.3 Ứng dụng phương pháp đếm giải các bài toán đồ thị 165 6.4 Ứng dụng đếm hai cách giải các bài toán rời rạc 167 6.5 Bài tập 169 171 Tài liệu tham khảo Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học Chương 1Tổng quan về hệ số nhị thức 1.1 Một số khái niệm 1 1.2 Các tính chất cơ bản 4 Hoàng Xuân Thanh (hxthanh) Tóm tắt nội dung Đẳng thức tổ hợp (ĐTTH) được giới thiệu trong bài viết này được hiểu là các đẳng thức có chứa các hệ số nhị thức (binomial coefficient) n . ĐTTH là một đề tài rất hay và khó, cùng với đó là rất nhiều k phương pháp tiếp cận khác nhau cho một bài toán. Trong phần này, tác giả sẽ hệ thống cho bạn đọc một số khái niệm và những công thức thường sử dụng. 1.1 Một số khái niệm 1.1.1 Hệ số nhị thức Định nghĩa 1.1 (Hệ số nhị thức) Hệ số nhị thức ký hiệu n k là hệ số của xktrong khai triển của nhị thức 1 2 1.1. Một số khái niệm xk. n (1 + x)n =Xn k=0 n k đọc là số tổ hợp n chập k (n choose k). 4 k Lưu ý rằng, một số quốc gia Châu Á trong đó có Việt Nam, thường ký hiệu tổ hợp n chập k là {kn. n Trong toàn bộ chuyên đề này chúng ta sử dụng ký hiệu quốc tế k Tính chất 1.1 (Quy ước)– n = 0 nếu k > n ≥ 0 hoặc k < 0 ≤ n. k Định lý 1.1 (Công thức giai thừa)– Với mọi số nguyên không âm n và k ta có n k =n! k!(n − k)! (1.1) với n! = 1.2...n trong đó quy ước 0! = 1. 1.1.2 Luỹ thừa giảm, lũy thừa tăng Định nghĩa 1.2 (Luỹ thừa giảm) Lũy thừa giảm n của x là xn = x(x − 1)...(x − n + 1) | {z } n nhân tử Quy ước x0 = 1. 4 Định nghĩa 1.3 (Luỹ thừa tăng) Lũy thừa tăng n của x là (x)n = x(x + 1)...(x + n − 1) | {z } n nhân tử Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 1.1. Một số khái niệm 3 Quy ước (x)0 = 1 4 n =nk k!=(−1)k(−n)k Tính chất 1.2– k k!=(n − k + 1)k k! 1.1.3 Khai triển nhị thức suy rộng với số mũ thực Định lý 1.2– Với mọi số thực x và s ta có (1 + x)s =X∞ k=0 s k xk(1.2) = 1 +s11! x +s22! x2 + · · · +sk k!xk + · · · (1.3) Chứng minh. Đặt f(x) = (1 + x)s, áp dụng khai triển Maclaurin cho f(x), ta có lần lượt f(0) = (1 + x)s x=0 = s0 f0(0) = s(1 + x)s−1 x=0 = s1 f00(0) = s2(1 + x)s−2 x=0 = s2 · · · = · · · f(k)(0) = sk Do đó f(x) = X∞ k=0 k!· xk =X∞ f(k)(0) k=0 sk k!· xk Vì lý do trên nên người ta mở rộng hệ số nhị thức cho “cơ số” thực s bất kỳ như sau: Định nghĩa 1.4 Với s ∈ R và k ∈ N s s k =sk k!=s(s − 1). . .(s − k + 1) k! xác định như trên được gọi là hệ số nhị thức mở rộng. 4 k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 4 1.2. Các tính chất cơ bản 1.2 Các tính chất cơ bản Tính chất 1.3 (Tính chất đối xứng)– Với mọi số nguyên n, k thoả mãn 0 ≤ k ≤ n ta có n k = n n − k Tính chất 1.4 (Công thức Pascal)– n k + n k + 1 = n + 1 k + 1 Chứng minh. Chứng minh trực tiếp từ công thức giai thừa. Từ công thức Pascal, người ta lập được bảng số sau, được gọi là Tam giác Pascal n n 0 n 1 n 2 n 3 n 4 n 5 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 ... · · · · · · · · · · · · · · · · · · • → • ↓ • Tam giác Pascal cho phép ta tính dần được các hệ số nhị thức. Mỗi số trong tam giác Pascal được xác định bởi tổng của hai số hạng hàng trên gần nhất phía bên trái (theo hướng mũi tên) Tính chất 1.5 (Tổng theo cột)– Xn k=0 k m = n + 1 m + 1 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 1.2. Các tính chất cơ bản 5 Ví dụ 1.1. n n 1 n 2 n 3 2 1 3 3 4 6 5 10 6 15 7 Chứng minh. 35 1 + 3 + 6 + 10 + 15 = 35 4 Xn k=0 k m =Xn k=0 k + 1 m + 1 − k m + 1 (Theo công thức Pascal) = = n + 1 m + 1 n + 1 m + 1 − 0 m + 1 (Sai phân) Tính chất 1.6 (Tổng theo đường chéo chính)– Xn k=0 m + k k = m + n + 1 n Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 6 1.2. Các tính chất cơ bản Ví dụ 1.2. n n 0 n 1 n 2 n 3 n 4 2 1 3 3 4 6 5 10 6 15 1 + 3 + 6 + 10 + 15 = 35 7 Chứng minh. Xn k=0 m + k k =Xn k=0 35 m + k m (Đối xứng) 4 = = m + n + 1 m + 1 m + n + 1 n (Tổng theo cột) (Đối xứng) Tính chất 1.7 (Tổng theo đường chéo phụ (số Fibonacci))– Xn k=0 n − k k = Fn+1 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 1.2. Các tính chất cơ bản 7 Ví dụ 1.3. n n 0 n 1 n 2 n 3 n 4 2 F6 F7 3 3 1 F8 4 4 6 4 5 1 5 10 6 1 6 7 1 Chứng minh. 1 + 4 + 3 = 8 = F6 1 + 5 + 6 + 1 = 13 = F7 1 + 6 + 10 + 4 = 21 = F8 4 Ta chứng minh đẳng thức trên bằng quy nạp theo n Với n = 1 và n = 2 dễ thấy các tổng là: 0 0 = 1 = F1 và 1 0 + 0 1 = 1 = F2 Giả sử đẳng thức đúng đến n − 1. Khi đó ta có: Xn k=0 n − k k =Xn k=0 n − 1 − k k − 1 n − 2 − k +Xn k=0 n − 1 − k k n − 1 − k (Pascal) = nX−2 k=0 k + nX−1 k=0 k = Fn−2 + Fn−1 (giả thiết quy nạp) = Fn (Công thức truy hồi dãy Fibonacci) Tính chất 1.8 (Quy tắc “hút” (absorption))– Với 0 < k ≤ n, ta có: n k =nk n − 1 k − 1 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 8 1.2. Các tính chất cơ bản Chứng minh. Chứng minh trực tiếp từ công thức giai thừa Tính chất 1.9 (Công thức lùi “cơ số”)– Với 0 ≤ k < n, ta có: n k =n n − k n − 1 k Chứng minh. Chứng minh trực tiếp từ công thức giai thừa. Tính chất 1.10– Tập con của tập con Với 0 ≤ k ≤ m ≤ n, ta có: n m m k = n k n − k m − k Chứng minh. Chứng minh trực tiếp từ công thức giai thừa Một đẳng thức cũng hay được dùng đến là đẳng thức Vandermonde Tính chất 1.11 (Đẳng thức Vandermonde (2 thừa số))– Cho các số nguyên không âm n, m, r. Ta có: n Xn k k=0 Chứng minh. m r − k = n + m r Dựa vào đẳng thức: (1 + x)n(1 + x)m = (1 + x)n+m Khai triển ra ta có: Xn k=0 n k xkXm j=0 m j xj = +m nX k=0 n + m k xk ⇔Xn k=0 Xm j=0 n k m j xj+k = +m nX k=0 n + m k xk Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 1.2. Các tính chất cơ bản 9 So sánh hệ số của xrở hai vế ta có: X j+k=r n k m j = n + m r ⇔Xn k=0 n k m r − k = n + m r Chứng minh tương tự ta có đẳng thức mở rộng sau: Tính chất 1.12 (Đẳng thức Vandermonde (mở rộng))– Cho các số nguyên không âm n1, . . . , nr, k = k1 + k2 + ... + kr. Ta có: X k1+k2+...+kr=k n1 k1 n2 k2 . . . nr kr = n1 + n2 + · · · + nr k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học Chương 2Phương pháp cân bằng hệ số chứng minh đẳng thức tổ hợp 2.1 Khai triển số thực 12 2.2 Ứng dụng số phức 22 Trần Trung Kiên (Ispectorgadget) Trần Quốc Nhật Hân (perfectstrong) Hoàng Xuân Thanh (hxthanh) Lê Kim Nhã (gogo123) Tóm tắt nội dung Phương pháp cân bằng hệ số là một trong những phương pháp khá hay và mạnh trong các bài toán tính tổng có chứa hệ số nhị thức. Cơ sở của phương pháp là việc đồng nhất hai đa thức bằng nhau (có thể là chuỗi luỹ thừa). Từ một hằng đẳng thức, ta khai triển thành đa thức theo 2 cách khác nhau, thì hai đa thức thu được vẫn phải là như nhau. Từ đó ta suy ra được hệ số của số hạng bậc nào đó trong 2 khai triển là bằng nhau, là điều cần chứng minh hoặc yêu cầu tính của đề bài. 11 12 2.1. Khai triển số thực 2.1 Khai triển số thực Ví dụ 2.1. Chứng minh đẳng thức 2n X 4 k=0 Lời giải. Xét đẳng thức (−1)k 2n k 2 = (−1)n 2n n (1 − x2)2n = (1 − x)2n(1 + x)2n(2.1) Khai triển Vế Trái của (2.1), ta có: 2n (1 − x2)2n =X k=0 2n k (−1)kx2k Hệ số của x2ntrong khai triển trên tương ứng với số hạng k = n là (−1)n 2n n . Khai triển Vế Phải của (2.1), ta được: 2n (1 − x)2n(1 + x)2n =X k=0 2n k 2n (−1)kxkX j=0 2n j xj 2n =X k=0 2n X j=0 (−1)k 2n k 2n j xj+k Như vậy, hệ số của x2ntrong khai triển trên tương ứng với các số hạng thoả k + j = 2n là X k+j=2n (−1)k 2n k 2n j 2n =X k=0 (−1)k 2n k 2n 2n − k 2n =X k=0 (−1)k 2n k 2 Từ đó suy ra đẳng thức cần chứng minh. Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.1. Khai triển số thực 13 Ví dụ 2.2. a) Chứng minh đẳng thức: Sn =Xn k=0 (−1)k n k 2n 2k =Xn k=0 (−1)k n k 3n n + k b) Tính S2m (m ∈ N) 4 Lời giải. Ta có đẳng thức: (1 − x2)n(1 + x)2n = (1 − x)n(1 + x)3n. Khai triển ra ta được: Xn k=0 (−1)k n k 2n x2kX j=0 2n j xj =Xn k=0 (−1)k n k 2n xkX j=0 3n j xj ⇔Xn k=0 2n X j=0 (−1)k n k 2n j x2k+j =Xn k=0 2n X j=0 (−1)k n k 3n j xi+j Tìm hệ số của x2ntrong cả hai khai triển trên ta có: X (−1)k n k 2n 2n − 2k =X (−1)k n k 3n 2n − k 2k+j=2n n 2n k+j=2n n 3n ⇔Xn k=0 (−1)k k 2k =Xn k=0 (−1)k k n + k Đẳng thức a) được chứng minh. Ta tiếp tục chứng minh đẳng thức b). Ta có: Sn =Xn k=0 (−1)k n k 3n n + k =Xn k=0 n!(3n)!(−1)k k!(n − k)!(n + k)!(2n − k)! =n!(3n)! (2n)!(2n)! Xn k=0 (2n)!(2n)!(−1)k k!(2n − k)!(n + k)!(n − k)! =n!(3n)! (2n)!(2n)! Xn k=0 (−1)k 2n k 2n n − k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 14 2.1. Khai triển số thực ⇒ S2m =(2m)!(6m)! (4m)!(4m)! Xét đẳng thức: X k+j=2m (−1)k 4m k 4m j (1 − x2)4m = (1 − x)4m(1 + x)4m 4m ⇔X k=0 (−1)k 4m k 4m x2k =X k=0 4m X j=0 (−1)k 4m k 4m j xk+j Cân bằng hệ số x2m ở đẳng thức trên ta có: Từ đó suy ra: (−1)m 4m m =X k+j=2m (−1)k 4m k 4m j (4m)!(4m)! ·(−1)m(4m)! S2m =(2m)!(6m)! m!(3m)! =(−1)m(2m)!(6m)! m!(3m)!(4m)! Ví dụ 2.3. Tìm hệ số x10 trong khai triển P(x) = (1 + x + x2 + x3)15 4 Lời giải (1). - Dùng hệ số nhị thức mở rộng P(x) = (1 − x4)15 (1 − x)15 = (1 − x)−15(1 − x4)15 =X∞ k=0 −15 k (−1)kxkX15 j=0 15 j (−1)jx4j =X 0≤j≤15 k≥0 (−1)j 14 + k k 15 j xk+4j Ta cần tìm hệ số x10, nghĩa là phải tìm tất cả nghiệm nguyên không âm của k + 4j = 10. Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.1. Khai triển số thực 15 Suy ra (j, k) ∈ {(0, 10); (1, 6); (2, 2)} Hệ số cần tìm có tất cả 3 số hạng tương ứng với (j, k) như trên là: 14 + 10 10 15 0 − 14 + 6 6 15 1 + 14 + 2 2 15 2 = 1 392 456 Lời giải (2). - Khai triển trực tiếp Một cách tổng quát: P(x) = (1 + x + x2 + x3)n = (1 + x)n(1 + x2)n =Xn n k xkXn n j x2j k=0 =Xn k=0 Xn j=0 n k j=0 n j xk+2j Hệ số của xm trong khai triển trên sẽ tương ứng với các số hạng thoả k + 2j = m hay k = m − 2j. Nghĩa là: hxmi(1 + x + x2 + x3)n =X j≥0 n j n m − 2j Ký hiệu: hxmi f(x) nghĩa là hệ số của xm trong khai triển f(x) Với n = 15 và m = 10, ta có: x10 (1 + x + x2 + x3)15 =X j≥0 15 j 15 10 − 2j = 15 0 15 10 + 15 1 15 8 + 15 2 15 6 + 15 3 15 4 + 15 4 15 2 + 15 5 15 0 = 1 392 456 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 16 2.1. Khai triển số thực Nhận xét. Bằng việc khai triển đẳng thức trên theo 2 cách khác nhau, ta thu được đẳng thức sau: X k+4j=m k,j∈N (−1)j n + k − 1 k n j =X k≥0 n k n m − 2k Ví dụ 2.4. Với các số tự nhiên m, n thoả m ≤ n. Chứng minh rằng: Xm k=0 m k k + n m =Xm k=0 m k n k 2k = (−1)mXm k=0 m k n + k k (−2)k 4 Lời giải. Ta tìm hệ số xntrong các khai triển: (−1)m[1−2(1+x)]m(1+x)n = (1+2x)m(1+x)n = [x+(1+x)]m(1+x)n (2.2) Ta có: (1 + 2x)m(1 + x)n =Xm m k 2kxkXn n j xj k=0 m j=0 =Xm k=0 Xn j=0 k n j 2kxk+j Hệ số của xn bao gồm tổng các số hạng thoả: k + j = n hay j = n − k. Đó là: Xm k=0 m k n n − k 2k(2.3) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.1. Khai triển số thực 17 Ta có tiếp: [x + (1 + x)]m(1 + x)n =Xm m k xm−k(1 + x)k+n k=0 =Xm k=0 m k xm−k nX+k j=0 n + k j xj =Xm k=0 nX+k j=0 m k n + k j xm−k+j Hệ số của xn bao gồm tổng các số hạng thoả: m − k + j = n hay j = n + k − m. Đó là: m Xm (2.4) k k=0 Tiếp theo: n + k n + k − m (−1)m[1 − 2(1 + x)]m(1 + x)n = (−1)mXm m k (−2)k(1 + x)k+n k=0 = (−1)mXm k=0 m k (−2)k nX+k j=0 n + k j xj = (−1)mXm k=0 nX+k j=0 m k n + k j (−2)kxj Như vậy hệ số của xntương ứng với j = n. Đó là: (−1)mXm k=0 m k n + k n (−2)k(2.5) Từ (2.2), (2.3), (2.4), (2.5) ta thu được các đẳng thức cần chứng minh. Ví dụ 2.5. Chứng minh đẳng thức: Xn k=0 4n−k 4n 2n + 2k 2n + 2k k = 8n 2n 4 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 18 2.1. Khai triển số thực Lời giải. Biểu thức của vế phải cho ta thấy đó là hệ số của số hạng thứ 2n + 1 trong khai triển của nhị thức với bậc 8n. Ta có: 8n (x + y)8n =X k=0 8n k x8n−kyk 8n Như vậy số hạng thứ 2n + 1 (tương ứng với k = 2n) là 2n x6ny2n Để cho đơn giản, ta cho y = x−1tức là 8n 2n =x4n (x + x−1)8n Ký hiệu hxni f(x) ở đây nghĩa là Hệ số của xntrong khai triển f(x) Ta có: 8n 2n =x4n (x + x−1)8n =x4n x2 + x−2 + 2 4n 4n =x4n X 4n k x2 + x−2 4n−k2k k=0 4n =x4n X k=0 4n =x4n X k=0 4Xn−k j=0 4Xn−k j=0 4n k 4n k 4n − k j 4n − k j 2kx8n−2k−2jx−2j 2kx8n−4j−2k Như vậy các số hạng chứa x4ntương ứng với k, j thoả 8n−4j−2k = 4n hay k = 2n − 2j, khi đó 0 ≤ 2n − 2j ≤ 2n ⇒ 0 ≤ j ≤ n Thay giá trị k = 2n − 2j và giới hạn của j vào biểu thức trên ta được: 8n 2n =Xn j=0 22n−2j 4n 2n − 2j 2n + 2j j =Xn k=0 4n−k 4n 2n + 2k 2n + 2k k Nhận xét. Cái hay của phương pháp này đó là: Bằng cách khai triển theo những cách khác nhau, ta có thể mở rộng được nhiều đẳng thức khác nhau từ bài toán ban đầu! Ví dụ: Từ đẳng thức: 8n 2n =x4n (x + x−1)8n Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.1. Khai triển số thực 19 Ta khai triển như sau: 4n (x + x−1)8n =2 + x2 + x−2 4n=X 4n k 24n−k(x2 + x−2)k k=0 4n =X k=0 4n =X k=0 Xk j=0 Xk j=0 4n k 4n k k j k j 24n−kx2k−2jx−2j 24n−kx2k−4j Từ đó: 2k − 4j = 4n hay 0 ≤ k = 2n − 2j ≤ 2n ⇒ 0 ≤ j ≤ n Do đó hệ số x4ncủa khai triển trên sẽ là: 4n x4n X k=0 Xk j=0 4n k k j 24n−kx2k−4j =Xn j=0 4n 2n − 2j 2n − 2j j 4n+j Từ đó ta có thêm đẳng thức: 8n 2n =Xn k=0 4n 2n + 2k 2n − 2k k 4n+k Bây giờ mà đảo chiều của tổng Vế Phải (thay k bởi n − k), ta có tiếp: 8n 2n =Xn k=0 4n 2k 2k n − k 42n−k Kết hợp với đề bài thì ta có đẳng thức Xn 4n−k 4n 2n + 2k 2n + 2k k =Xn 42n−k 4n 2k 2k n − k k=0 Lưu ý rằng Như vậy: 2k n − k k=0 chỉ 6= 0 khi 2k ≥ n − k hay k ≥n3 Xn k=0 42n−k 4n 2k 2k n − k =Xn k=bn+2 3 c 42n−k 4n 2k 2k n − k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 20 2.1. Khai triển số thực Ví dụ 2.6. Với các số nguyên n, m thoả 0 ≤ m ≤ n. Chứng minh đẳng thức: 2n−m 4 Lời giải. bn−m X2 c k=0 (−1)k n k 2n − 2k n + m = n m Quan sát vế phải của đẳng thức cần chứng minh ta thấy rằng: n m 2n−m = hxmi(2 + x)n 2n − 2k Mặt khác quan sát thấy vế phải của đẳng thức có nhị thức n + m , điều này chứng tỏ biểu thức đó là hệ số bậc (n+m) của một khai triển bậc cao hơn n Do đó ta sẽ nhân thêm xnvào khai triển trên hxmi(2 + x)n =xn+m (2x + x2)n =xn+m [(x + 1)2 − 1]n =xn+m Xn n k (x + 1)2(n−k)(−1)k k=0 =xn+m Xn k=0 2nX−2k j=0 n k 2n − 2k j (−1)kxj Suy ra j = n + m và do đó ta có: n m 2n−m =Xn k=0 (−1)k n k 2n − 2k n + m Để ý rằng với k > n − m 2thì 2n−2k < n+m và khi đó 2n − 2k n + m = 0 Từ đó ta có đẳng thức cần chứng minh Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.1. Khai triển số thực 21 Bài tập Bài 1. Cho các số tự nhiên m, n thoả mãn m ≤ 2n Chứng minh đẳng thức Xm k=0 2n 2k 2n − 2k m − k 4k = 4n 2m Bài 2. Cho các số tự nhiên m, n thoả mãn 2m + 1 ≤ 3n Chứng minh đẳng thức Xn k=0 (−1)k n k n + 2m − 4k n − 1 =Xn k=0 n k n 2m + 1 − 2k Bài 3. Chứng minh đẳng thức Xn k=0 (−3)k 2n k 2n − k n − k = (−2)n 2n n Bài 4. Chứng minh đẳng thức bnX2 c k=0 n k n − k k =Xn k=0 (−1)k n k 2n − 2k n − k Bài 5. Chứng minh đẳng thức Xn k=0 (−1)k2k n k 2 = 2nXn k=0 (−1)k n k 2n k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 22 2.2. Ứng dụng số phức 2.2 Ứng dụng số phức Việc tính tổng hoặc chứng minh đẳng thức chứa các hệ số nhị thức, đôi khi ta cũng cần dùng đến công cụ số phức. Vậy khi nào ta cần dùng đến số phức? Đó là những tổng có dạngXn k=0 p > 1 f(m, pk) hoặc Xn k=0 (−1)k.f(m, pk) với Ý nghĩa của những tổng dạng trên đó là “khoảng cách” giữa hai số hạng liên tiếp là một bội của biến chạy k. Ví dụ:Xn k=0 (−1)k 2n 2k ;Xn k=0 3n 3k ; v.v... Tại sao ta cần dùng số phức? Ta cần đến tính chất gì của số phức? Để trả lời cho câu hỏi trên, chúng ta hãy cùng tìm hiểu một số vấn đề sau: Ta có i2 = −1; i2n = (−1)n; . . . . Xét phương trình xn − 1 = 0 (2.6) Phương trình (2.6) có nghiệm x =√n1. Những nghiệm này (cả nghiệm phức) bao gồm n giá trị {1; ε; ε2; ...; εn−1} trong đó: ε = cos 2π n + isin 2π n Mặt khác: xn − 1 = (x − 1)(xn−1 + xn−2 + ... + x + 1) Như vậy ngoại trừ nghiệm x = 1 thì n − 1 nghiệm phức còn lại đều thoả mãn phương trình: xn−1 + xn−2 + ... + x + 1 = 0 (2.7) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 23 Thay lần lượt các giá trị nghiệm vào (2.7), ta được: εn−1 + εn−2 + ... + ε + 1 = 0 ε2(n−1) + ε2(n−2) + ... + ε2 + 1 = 0 . . . Một cách tổng quát ta có Định lý 2.1 (Định lý RUF - Root of Unity Filter)– 1 n X εn=1 εk = ( 1 nếu n | k 0 nếu n - k Hiểu một cách đơn giản là: Trung bình cộng với luỹ thừa bậc k của n giá trị căn phức bậc n của 1 bằng 1 nếu k là bội của n, ngược lại giá trị này bằng 0. Ngoài ra một tính chất rất cơ bản đó là: ( z1 = z2 ⇔ Re(z1) = Re(z2) Im(z1) = Im(z2) Để tìm hiệu cách sử dụng các tính chất trên như thế nào, ta hãy xét một số ví dụ sau: Ví dụ 2.7. Tính tổng S =Xn k=0 (−1)k 2n 2k 4 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 24 2.2. Ứng dụng số phức Lời giải. Xét khai triển (1 + i)2n, ta có: 2n (1 + i)n =X k=0 =Xn 2n k 2n 2k ik i2k +Xn 2n 2k − 1 i2k−1 k=0 =Xn k=0 (−1)k 2n 2k k=1 +Xn k=1 i.(−1)k−1 2n 2k − 1 Như vậy ta dễ dàng nhận ra được: S =Xn k=0 (−1)k 2n 2k = Re[(1 + i)2n] Và nhân tiện ta cũng có luôn: = Im[(1 + i)2n] Mặt khác: Xn k=1 (−1)k−1 2n 2k − 1 (1 + i)2n =h√2 cosπ4+ isinπ4 i2n= 2n cosnπ2+ isinnπ2 Từ đó suy ra: S =Xn k=0 (−1)k 2n 2k = 2ncosnπ2 và:Xn k=1 (−1)k−1 2n 2k − 1 = 2nsinnπ2 Nhận xét. Liệu bài toán này có phải bắt buộc phải dùng công cụ số phức? Các bạn thử tìm cách khác xem nhé! Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 25 Ví dụ 2.8. Tính tổng Lời giải. 3n S =X k=0 12n 4k 4 Nhìn vào đề bài, gợi ý cho ta liên hệ ngay đến khai triển (1 + i)12n? Nhưng liệu có ra được kết quả cuối cùng không? Ta hãy tính thử xem! 12n (1 + i)12n =X k=0 12n k ik Các số hạng của ta “cách đều” một khoảng bội của 4, như vậy một cách tự nhiên ta sẽ tách khai triển trên thành 4 tổng theo phân đoạn module 4 (theo k mod 4) 12n X k=0 12n k 3n ik =X k=0 12n 4k i4k + 3Xn−1 k=0 12n 4k + 1 i4k+1 + 3Xn−1 k=0 12n 4k + 2 i4k+2 + 3Xn−1 k=0 12n 4k + 3 i4k+3 3n =X 12n 4k + i 3Xn−1 12n 4k + 1 k=0 3Xn−1 − k=0 12n 4k + 2 k=0 − i 3Xn−1 k=0 12n 4k + 3 Đến đây, ta gặp một “vướng mắc nhỏ”, đó là: 3n Re (1 + i)12n =X k=0 12n 4k − 3Xn−1 k=0 12n 4k + 2 (2.8) Như vậy là so với tổng cần tính giá trị của ta “thừa ra” một tổng ... tương tự. Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 26 2.2. Ứng dụng số phức Không vấn đề gì, trở lại với số thực ta xét khai triển: 12n (1 + x)12n =X k=0 3n =X 12n k 12n 4k xk x4k + 3Xn−1 12n 4k + 1 x4k+1 k=0 12n k=0 12n x4k+3 + và 3Xn−1 k=0 4k + 2 x4k+2 + 3Xn−1 k=0 4k + 3 12n (1 − x)12n =X k=0 3n =X 12n k 12n 4k (−1)kxk 3Xn−1 x4k − 12n 4k + 1 x4k+1 k=0 12n k=0 12n + 3Xn−1 k=0 4k + 2 x4k+2 − 3Xn−1 k=0 4k + 3 x4k+3 Cộng 2 đẳng thức trên theo từng vế ta được: 3n (1 + x)12n + (1 − x)12n = 2X k=0 Cho x = 1, thì ta được: 12n 4k x4k + 2 3Xn−1 k=0 12n 4k + 2 x4k+2 3n 212n = 2X k=0 12n 4k + 2 3Xn−1 k=0 12n 4k + 2 hay 3n 212n−1 =X k=0 12n 4k + 3Xn−1 k=0 12n 4k + 2 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 27 Cộng vế theo vế với (2.8), ta sẽ có: 3n 212n−1 + Re (1 + i)12n = 2X k=0 Việc còn lại ta chỉ phải tìm Re (1 + i)12n . Ta có: 12n 4k = 2S (1 + i)12n =h√2 cosπ4+ isinπ4 i12n = 26n(cos(3nπ) + isin(3nπ)) = (−1)n26n Từ đó ta có: 3n S =X k=0 12n 4k = 212n−2 + (−1)n26n−1 Nhận xét. Ngoài ra ta còn thu được đẳng thức: Im (1 + i)12n =3Xn−1 k=0 12n 4k + 1 − 3Xn−1 k=0 12n 4k + 3 = 0 hay 3Xn−1 k=0 12n 4k + 1 = 3Xn−1 k=0 12n 4k + 3 (2.9) Thêm một câu hỏi cho các bạn: Tổng (2.9) bằng bao nhiêu? Ví dụ 2.9. Cho n ∈ N. Chứng minh rằng 1 − n 2 + n 4 − · · · 2 + n 1 − n 3 + n 5 + · · · 2 = 2n4 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 28 2.2. Ứng dụng số phức Lời giải (1). Ta có: (1 + i)n = Lại có: 1 − n 2 + n 4 + · · · + i n 1 − n 3 + n 5 + · · · (1 + i)n =√2n cosnπ4+ sinnπ4 =√2n cosnπ4+√2n sinnπ4 Do đó: 1 − n 2 + n 4 + · · · 2 = 2n cosnπ4 2 n 1 − n 3 + n 5 − · · · 2 = 2n sinnπ4 2 Cộng 2 đẳng thức trên, ta có đẳng thức cần chứng minh. Lời giải (2). Xét số phức z = 1 + i. Khi đó zn = (1 + i)n =Xn n k ik n k=0 n n n n = Suy ra 1 − 2 n + 4 n + · · · + i 2 1 n − 3 n + 5 n − · · · 2 |zn|2 = 1 − 2 + 4 + · · · + 1 − 3 + 5 − · · · Mà |zn| = |z|n = √2 n. Từ đó ta có được đpcm. Ví dụ 2.10. Tính tổng A = 3n 2n 0 − 3n−1 2n 2 + ... + (−1)n−13 2n 2n − 2 + (−1)n 2n 2n B = 32m 4m 0 + 32m−2 4m 4 + 32m−4 4m 8 + ... + 32 4m 4m − 4 + 4m 4m 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 29 Lời giải. Xét các khai triển (√3)2n−kxk (√3)2n−k(−1)kxk Vậy 2n (√3 + x)2n =X k=0 2n (√3 − x)2n =X k=0 2n k 2n k T = 3n 2n 0 + 3n−1x2 2n 2 + 3n−2x4 2n 4 + ... + +x2n 2n 2n =12h(√3 + x)2n + (√3 − x)2ni Chọn x = i thì (√3 + i)2n = 22n cosπ6+ isinπ6 2n= 22n cosnπ3+ isinnπ3 (√3 − i)2n = 22n cos −π6 + isin −π6 2n= 22n cosnπ3− isinnπ3 Suy ra A = 22ncosnπ3. Với n = 2m, chọn x = 1 thì A0 = 32m 4m 0 + 32m−1 4m 2 + 33m−2 4m 4 + ... + 3 4m 4m − 2 + 4m 4m = 22m−1[(2 + √3)2m + (2 −√3)2m] A = 32m Do đó 4m 0 − 32m−1 4m 2 + 32m−2 4m 4 + ... + 4m 4m = 24m cos2mπ 3 B =A + A0 2= 22m−2[(2 + √3)2m + (2 −√3)2m] + 44m−1cos2mπ 3 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 30 2.2. Ứng dụng số phức Ví dụ 2.11. Chứng minh n 0 + n 3 + n 6 + n 9 + ... =13 2n + 2 cosπn3 n 1 n 2 Lời giải. + + n 4 n 5 + + n 7 n 8 + + n 10 n 11 + ... =13 2n + 2 cosn − 2 3π + ... =13 2n + 2 cosn − 4 3π 4 Ta có: 1 + cos ϕ + isin ϕ = 2 cosϕ2 cosϕ2+ isinϕ2 Đặt ε = cos2π3+ isin2π3, ta có εk = 1 ⇔ k = 3m và 1 + εk + ε2k =1 − ε3k 1 − εk= 0 với mọi k không là bội của 3. Xét các khai triển 2n = (1 + 1)n = n 0 + n 1 + ... + n n − 1 + n n (1 + ε)n = n 0 + ε n 1 + ... + εn−1 n n − 1 + εn n n (1 + ε)2n = Ta có: n 0 + ε2 n 1 + ... + ε2n−2 n n − 1 + ε2n n n (1 + ε)n = (1 + ε2)n = 1 + cos2π3+ isin2π3 n= 2ncosn π3 cosnπ3+ isinnπ3 1 + cos4π3+ isin4π3 n= 2ncosn2π3 cos2nπ 3+ isin2nπ 3 = 2ncosn π3 cosπn3− isinnπ3 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 31 Gọi vế trái các đẳng thức cần chứng minh lần lượt là S1, S2, S3 thì 3S1 = (1 + 1)n + (1 + ε)n + (1 + ε2)n = 2n + 2.2ncosn π3cosnπ3 Hay n 0 + n 3 + n 9 + ... =13 2n + 2 cosnπ3 Suy ra 3S1 = (1 + 1)n + ε2(1 + ε)n + ε(1 + ε2)n = 2n + ε2 cosnπ2+ isinnπ3 + ε cos2nπ 3+ isin2πn 3 n 1 + n 4 + n 7 +... =13 2n + 2 cosn − 2 3π Suy ra = 2nε2 cosnπ3+ isinnπ3 + ε cos2nπ 3+ isin2nπ 3 n 2 + n 5 + n 8 + n 11 + ... =13 2n + 2 cosn − 4 3π Nhận xét. Điểm mấu chốt của lời giải là sử dụng tính chất căn bậc 3 của đơn vị và công thức Moivre. Chúng ta xét thêm một ví dụ nữa để làm rõ hơn nữa cách giải dạng toán này (Hoàn toàn tương tự cho lời giải bài toán tổng quát). Ví dụ 2.12. Tính tổng + ...4 Lời giải. S = n 0 + n 6 + n 12 + n 18 Khoảng cách của hai chỉ số trên liên tiếp là 6 nên xét số phức ε = cos2π6+ isin2π6= cosπ3+ isinπ3 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 32 2.2. Ứng dụng số phức Ta thấy εk = 1 khi và chỉ khi k là bội của 6, và với mọi k không chia hết cho 6 thì 1 + εk + ε2k + ε3k + ε4k + ε5k =1 − ε6k 1 − εk= 0 Ta có: (1 + 1)n + (1 + ε)n + (1 + ε2)n + (1 + ε3)n + (1 + ε4)n + (1 + ε5)n = 6S Rõ ràng ε = cosπ3− isinπ3, ε3 = −1 và ε6 = 1 = ε.ε nên ε6−p = εp Do đó: (1 + ε5)n = (1 + ε)n, (1 + ε4)n = (1 + ε2)n 1 + ε =√3 cosπ6+ isinπ6 1 + ε =√3 cosπ6− isinπ6 1 + ε2 = cosπ3+ isinπ3 1 + ε2 = cosπ3− isinπ3 Suy ra 6S = 2n + (1 + ε)n + (1 + ε)n + (1 + ε2)n + (1 + ε2)n = 2n + (√3)n cosnπ6+ isinnπ6 + (√3)n cosnπ6+ isinnπ6 = 2n + 2(√3)ncosnπ6+ 2 cosnπ3 Vậy ta có: S =13h2n−1 + (√3)ncosnπ6+ cosnπ3i Ví dụ 2.13. Tính tổng T2 = 1 8n 1 − 3 8n 3 + ... − (8n − 1) 8n 8n − 1 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 33 Lời giải. Trước tiên ta phải dùng đạo hàm để có được hệ số đứng trước tổ hợp. Xét đa thức f(x) = (1 + x)8n = 8n 0 8n +X k=1 n k xk 8n ⇒ f0(x) = 8n(1 + x)8n−1 =X k k=0 n k xk−1 8n n Lại nhân với x ta đươc g(x) = 8nx(1 + x)8n−1 =X k k k=0 thấy T2 chính là phần ảo của g(i) = 8ni(1 + i)8n−1 = 4n.16n + 4n.16ni Do đó T2 = 4n.16n Tương tự ta dùng đạo hàm 2 lần để tính tổng xk Nhận 22 8n 2 − 42 8n 4 + 62 8n 6 − ... − (8n)2 8n 8n (1 + x)8n = 8n 0 8n +X k=1 8n k xk 8n ⇒ 8n(1 + x)8n−1 =X k k=1 8n ⇔ 8nx(1 + x)8n−1 =X k 8n k 8n k xk−1 xk k=1 8n ⇒ 8n(1 + x)8n−2(1 + 8nx) =X k2 k=1 8n ⇔ 8nx(1 + x)8n−2(1 + 8nx) =X k2 k=1 8n k 8n k xk−1 xk = f(x) Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 34 2.2. Ứng dụng số phức Tổng cần tìm chính là phần thực của f(i) = 8nf(1 + i)8n−2(1 + 8ni) = 16n−1 + 128n2.16n−2i. Ví dụ 2.14 (T7/248-THTT). Chứng minh đẳng thức sau với n là số nguyên dương:  X 0≤2k≤n Lời giải. (−1)k n 2k   2 +  X 0≤2k+1≤n (−1)k n 2k + 1   2 = 2n 4 Xét số phức z = 1 + i, sử dụng khai triển nhị thức Newton ta có zn = (1 + i)n =Xn k=0 ik n k n n =X 0≤2k≤n Lấy module hai vế (−1)k 2k + i. X 0≤2k+1≤n (−1)k 2k + 1 |zn| = Mặt khác: vuuutX 0≤2k≤n (−1)k n 2k   2 +  X 0≤2k≤n (−1)k n 2k + 1   2 zn =h√2 cosπ4+ isinπ4 in=√2n cosnπ4+ isinnπ4 Từ đó ta có |zn|2 = 2n, là điều phải chứng minh Chú ý: Nếu số phức z = cos ϕ + isin ϕ thì: zn = (cos ϕ + isin ϕ)n = cos nϕ + isin nϕ Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 35 (cos ϕ + isin ϕ)n =X (−1)k n 2k . cosn−2k ϕ sin2k ϕ 0≤2k≤n + i. X 0≤2k+1≤n Do đó lấy module hai vế ta có: (−1)k n 2k + 1 cosn−2k−1 ϕ sin2k+1 ϕ  X 0≤2k≤n (−1)k n 2k  . cosn−2k ϕ sin2k ϕ   2  + X 0≤2k≤n (−1)k n 2k + 1 . cosn−2k−1 ϕ sin2k+1 ϕ  2 = 1 Xét ϕ =π4ta có kết quả bài toán trên. Xét ϕ =π3thì cosπ3=12, sinπ3=√32nên ta có đẳng thức:  X 0≤2k≤n (−3)k n 2k   2 + 3  X 0≤2k+1≤n (−3)k n 2k + 1   2 = 4n Ví dụ 2.15. Chứng minh rằng Xn k=0 n k 2 cos kx = bnX2 c k=0 n 2k 2k k 2 cosx2 n−2kcosnx2, x ∈ [0; π] 4 Lời giải. Đặt An =Xn k=0 n k 2 cos kx, Bn =Xn k=0 n k 2 sin kx Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 36 2.2. Ứng dụng số phức Ta có: An + iBn =Xn k=0 n k 2 (cos kx + isin kx) = Xn k=0 n k 2 (cos x + isin x)k Xét hệ số yntừ hằng đẳng thức (1+y)n(1+zy)n = [1+ (1+z)y+zy2]n ta cóX k+l=n 0≤k,l≤n n k . n l zl =X k+l+s=n 0≤k,l,s≤n n! k!l!s!(z + 1)lzs Hay viết lại dưới dạng Xn k=0 n k 2 zk = bnX2 c k=0 n 2k 2k k (z + 1)n−2kzk Xét z = cos x + isin x thì 1 + z = 1 + cos x + isin x = 2 cosx2 cosx2+ isinx2 nên với x ∈ [0; π] ta có An + iBn =Xn k=0 =Xn k=0 n k n k 2 2 (cos x + isin x)k zk = bnX2 c k=0 n 2k 2k k (z + 1)n−2kzk = bnX2 c k=0 n 2k 2k k 2 cosx2 n−2k cosx(n − 2k) 2 +isinx(n − 2k) 2 (cos kx + isin kx) = bnX2 c k=0 n 2k . 2k k 2. cosx2 n−2k cosnx2+ isinnx2 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 37 Vì thế An = bnX2 c k=0 n 2k 2k k 2 cosx2 n−2kcosnx2 Bn = bnX2 c k=0 n 2k 2k k 2 cosx2 n−2ksinnx2 Vậy ta có đpcm. Nhận xét. Theo kết quả trên thì Xn k=0 n k 2 sin kx = bnX2 c k=0 n 2k 2k k 2 cosx2 n−2ksinnx2 Nếu x = 0 thì Xn k=0 Nếu x = π thì n k 2 = bnX2 c k=0 n 2k 2k k 2n−2k = 2n n Xn n 2  0, n = 2m + 1 (−1)k k=0 k =  (−1) n2 n n 2 n = 2mm ∈ N Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 38 2.2. Ứng dụng số phức Bài tập Bài 1. Cho n, k là hai số nguyên dương với n > 2k + 1, chứng minh rằng: a) X j≥0 n j(2k + 1) =2n 2k + 1 " 1 + 2 Xk m=1 cosmπ 2k + 1 n cosmnπ 2k + 1 # b) X j≥0 n j2k =2n 2k " 1 + 2 Xk m=1 cosmπ 2k + 1 n cosmnπ 2k + 1 # c) (Tổng quát) X r≥0 n j + rk =2nkkX−1 m=0 cosmπk ncos(n − 2j)mπ k Bài 2. Cho các dãy số an, bn, cn được xác định theo công thức: + ... + ... + ... Chứng minh rằng: an = bn = cn = n 0 n 1 n 2 + + + n 3 n 4 n 5 + + + n 6 n 7 n 8 a) a3n + b3n + c3n − 3anbncn = 2n b) a2n + b2n + c2n − anbn − bncn − ancn = 1 Bài 3. Cho số nguyên dương n và các số thực x, y. Chứng minh rằng: a) Xn n 2cosn(x + y) k=0 b) Xn k n cos[(n − k)x + ky] = 2ncosn x − y 2 sin[(n − k)x + ky] = 2ncosn x − y k=0 k 2sinn(x + y) 2 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 2.2. Ứng dụng số phức 39 Bài 4. Cho khai triển (x2 + 3x + 1)10 = a0 + a1x + a2x2 + ... + a20x20. Tính tổng a) T1 = a0 + a4 + a8 + ... + a20 b) T2 = a1 + a5 + a9 + ... + a17 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học Chương 3Tính tổng, chứng minh ĐTTH bằng phương pháp Sai phân từng phần 3.1 Sai Phân (Difference) 42 3.2 Sai Phân Từng Phần 43 3.3 Một số bài toán và Ví dụ minh hoạ 44 3.4 Bài tập tự luyện 68 Nguyễn Bảo Phúc (dark templar) Trần Quốc Nhật Hân (perfectstrong) Hoàng Xuân Thanh (hxthanh) Tóm tắt nội dung Sai Phân Từng Phần (tên gọi do tác giả tự đặt) còn được biết đến với cái tên Summation by Parts. Đây là một phương pháp tính tổng có cấu trúc gần giống với phương pháp Tích Phân Từng Phần (Integration by Parts). Sai phân từng phần (SPTP) là một trong những công cụ sơ cấp khá hiệu quả trong các bài toán tính tổng hữu hạn. Trong khuôn khổ bài viết này, tác giả muốn giới thiệu đến bạn đọc một trong những ứng dụng của SPTP đó là: Sử dụng phương pháp SPTP trong các bài toán tính tổng hoặc chứng minh đẳng thức Tổ Hợp. 41 42 3.1. Sai Phân (Difference) 3.1 Sai Phân (Difference) Định nghĩa 3.1 (Sai Phân) Cho dãy f(k) : {f(1), f(2), ..., f(k), f(k + 1), ...} Khi đó dãy ∆f(k) : {f(2) − f(1), f(3) − f(2), ..., f(k + 1) − f(k), ...} được gọi là Dãy Sai Phân của f(k) Một cách đơn giản, ta gọi: ∆f(k) = f(k + 1) − f(k) là Sai Phân (cấp 1) của f(k) 4 Tính chất 3.1 (cơ bản)– ∆(C) = 0 (C = const) (3.1) ∆ [Cf(k)] = C∆f(k) (C = const) (3.2) ∆ [f(k) + g(k)] = ∆f(k) + ∆g(k) (3.3) Định lý 3.1 (Tổng Sai Phân)– b+1 Xb k=a= f(b + 1) − f(a) k=a Chứng minh. ∆f(k) = f(k) Xb k=a ∆f(k) = [f(a + 1) − f(a)] + [f(a + 2) − f(a + 1)] + ... + [f(b + 1) − f(b)] = f(b + 1) − f(a) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.2. Sai Phân Từng Phần 43 Ví dụ 3.1.Xn k=0 Theo 3.1 ta có 2k =Xn k=0 (2k+1 − 2k) = Xn k=0 ∆2k Xn k=0 ∆2k = 2n+1 − 20 = 2n+1 − 1 4 Ví dụ 3.2. Với số n là số nguyên dương Xn (−1)k n k =Xn (−1)k n − 1 k − (−1)k−1 n − 1 k − 1 k=0 Theo 3.1 ta có k=0 =Xn k=0 ∆ (−1)k−1 n − 1 k − 1 Xn k=0 ∆ (−1)k−1 n − 1 k − 1 = (−1)k−1 n − 1 k − 1 n+1 k=0 = 0 4 3.2 Sai Phân Từng Phần Định lý 3.2 (SPTP)– Xb k=a g(k).∆f(k) = g(k)f(k) b+1 k=a −Xb k=a f(k + 1).∆g(k) Chứng minh. Đặt h(k) = g(k).f(k) Ta có: ∆h(k) = g(k + 1).f(k + 1) − g(k).f(k) = g(k + 1).f(k + 1) − g(k).f(k + 1) + g(k).f(k + 1) − g(k)f(k) = f(k + 1)∆g(k) + g(k)∆f(k) Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 44 3.3. Một số bài toán và Ví dụ minh hoạ Lấy tổng hai vế từ a đến b, ta được: Xb g(k).∆f(k) = Xb ∆h(k) −Xb f(k + 1).∆g(k) k=a k=a = g(k)f(k) b+1 k=a k=a −Xb k=a f(k + 1).∆g(k) Trường hợp g(k) ≡ 1 ta có được hệ quả là công thức 3.1 Vấn đề của việc tính tổng bằng phương pháp SPTP 3.2 là phải “nhìn thấy” sai phân ∆f(k) trong biểu thức lấy tổng mà đề bài cho. Đó quả thực là một điều không hề đơn giản và hết sức thú vị của phương pháp này! 3.2.1 Một số sai phân thường dùng 2k = ∆(2k) (3.4) ak = ∆ ak a − 1 (a 6= 1) (3.5) mkm−1 = ∆ (km) (3.6) (−1)k n k = ∆ (−1)k−1 n − 1 k − 1 (3.7) n + k n = ∆ n + k n + 1 (3.8) 3.3 Một số bài toán và Ví dụ minh hoạ Ví dụ 3.3. Tính tổng: S =Xn k=1 k n + k k 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 45 Lời giải. Ta có:  n + k k = n + k n = n + k + 1 n + 1 − n + k n + 1  = ∆ n + k n + 1 = ∆f(k) ∆g(k) = ∆(k) = k + 1 − k = 1 Từ đó, áp dụng SPTP 3.2 ta được: S = k n + k n + 1 n+1 k=1 −Xn k=1 n + k + 1 n + 1 = (n + 1) 2n + 1 n + 1 2n + 1 − 1 −Xn k=1 ∆ n + k + 1 n + 2 = (n + 1) = (n + 1) Ví dụ 3.4. Tính tổng: n + 1 2n + 1 n + 2 − 1 − 2n + 2 n + 2 − 1 S =Xn k=0 (−1)k n k n + k k 4 Nhận xét. Trong biểu thức lấy tổng đã cho, cả hai thừa số đều có thể dễ dàng viết được dưới dạng sai phân. Vì vậy ta phải cân nhắc việc chọn một trong hai cách để tiếp cận. Giả sử ta làm như sau: Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 46 3.3. Một số bài toán và Ví dụ minh hoạ Lời giải (Lời giải 1).  (−1)k n k = (−1)k n − 1 k − (−1)k−1 n − 1 k − 1 = ∆ (−1)k−1 n − 1 k − 1 = ∆f(k)  ∆g(k) = ∆ n + k k = n + k + 1 k + 1 − n + k k = n + k k + 1 Từ đó, áp dụng SPTP 3.2 ta được: S = (−1)k−1 n − 1 k − 1 n + k k n+1 k=0 −Xn k=0 (−1)k n − 1 k n + k k + 1 = nX−1 k=0 (−1)k+1 n − 1 k n + k k + 1 Quan sát sự thay đổi của tổng sau 1 lần áp dụng SPTP thì ta thấy rằng, nếu đặt: S(m,n) = nX−m k=0 (−1)k+m n − m k n + k k + m rồi áp dụng SPTP 3.2 như trên ta sẽ có:  (–1)k+m n − m k = (–1)k+m n − m − 1 k − (–1)k+m−1 n − m − 1 k − 1 = ∆ (−1)k+m−1 n − m − 1 k − 1 = ∆f(k)  ∆g(k) = ∆ n + k k + m = n + k + 1 k + m + 1 − n + k k + m = n + k k + m + 1 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 47 Theo 3.2 ta được: S(m,n) = (−1)k+m−1 n − m − 1 k − 1 n + k k + m n−m+1 k=0 − nX−m (−1)k+m n − m − 1 k n + k k + m + 1 = k=0 n−Xm−1 k=0 (−1)k+m+1 n − m − 1 k n + k k + m + 1 = S(m+1,n) Từ đó ta có: S = S(0,n) = S(1,n) = ... = S(n,n) = nX−n k=0 (−1)k+n n − n k n + k k + n = (−1)n Lời giải (2). Ta có:  n + k n = n + k + 1 n + 1 − n + k n + 1 = ∆ n + k n + 1 = ∆f(k)  ∆g(k) = ∆ (−1)k n k = (−1)k+1 n k + 1 − (−1)k n k = (−1)k+1 Từ đó, áp dụng SPTP 3.2 ta được: n + 1 k + 1 S = n + k n + 1 (−1)k n k n+1 −Xn (−1)k+1 n + 1 k + 1 n + k + 1 n + 1 n + 1 k=0 k=0 =Xn k=0 (−1)k k + 1 n + 1 + k n + 1 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 48 3.3. Một số bài toán và Ví dụ minh hoạ Quan sát sự thay đổi của tổng sau 1 lần áp dụng SPTP thì ta thấy rằng, nếu đặt: S0(m,n) =Xn k=0 (−1)k m n − k m + k m rồi áp dụng SPTP 3.2 như trên ta sẽ có:  m + k m = m + k + 1 m + 1 − m + k m + 1 = ∆ m + k m + 1 = ∆f(k)  ∆g(k) = ∆ (–1)k m n − k = (–1)k+1 m n − k − 1 − (–1)k m n − k Theo 3.2 ta được: = (−1)k+1 m + 1 n − k S0(m,n) = m + k m + 1 (−1)k m n − k n+1 −Xn (−1)k+1 m + 1 n − k k=0 m + 1 + k m + 1 k=0 m + 1 m + 1 + k =Xn k=0 (−1)k n − k m + 1 = S0(m+1,n) Từ đó ta có: S = S0(n,n) = S0(n−1,n) = ... = S0(0,n) =Xn k=0 = (−1)n (−1)k 0 n − k 0 + k 0 (Chỉ có số hạng cuối cùng khác 0) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 49 Nhận xét. Phải nói là ta đã gặp may mắn khi tiếp cận bài này theo cách thứ hai. Trong đa số trường hợp, việc “nhìn thấy” sai phân từ biểu thức lấy tổng mang yếu tố quyết định xem có thể giải bài toán theo phương pháp SPTP được không! Ví dụ 3.5. Tính tổng: S =Xn (−1)k n k 2k + 1 4 k=0 Lời giải. Ta có:  (–1)k n k = (–1)k n − 1 k + (–1)k n − 1 k − 1 = ∆ (–1)k−1 n − 1 k − 1  ∆ 1 2k + 1 =1 2k + 3−1 2k + 1= −2 (2k + 3)(2k + 1) Áp dụng SPTP 3.2 cho S, ta được S =(−1)k−1 2k + 1 n − 1 k − 1 n+1 k=0 −Xn k=0 (−1)k n − 1 k −2 (2k + 3)(2k + 1) = nX−1 k=0 (−1)k n − 1 k 2 (2k + 3)(2k + 1) = S1 Tương tự, ta có:  n–1 n–2 n–2 n − 2 (–1)k k = (–1)k k + (–1)k k–1 = ∆ (–1)k−1 k − 1 2 (2k + 5)(2k + 3) −2  ∆ (2k + 3)(2k + 1) =2 = −2.4 (2k + 3)(2k + 1) (2k + 5)(2k + 3)(2k + 1) Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 50 3.3. Một số bài toán và Ví dụ minh hoạ Áp dụng SPTP 3.2 cho S1, ta được S1 =2(−1)k−1 (2k + 3)(2k + 1) n − 2 k − 1 nk=0 − nX−1 k=0 (−1)k n − 2 k −2.4 (2k + 5)(2k + 3)(2k + 1) = nX−2 k=0 (−1)k n − 2 k 2.4 (2k + 5)(2k + 3)(2k + 1) = S2 · · · Tiếp tục quá trình trên, cuối cùng ta thu được: S = S1 = ... = Sn = nX−n k=0 (–1)k n–n k 2.4...(2n) (2k+2n+1)(2k+2n–1)...(2k+1) =(2n)!! (2n + 1)!! Ví dụ 3.6. Cho dãy Fibonacci ( F0 = 0; F1 = 1 Fn+2 = Fn+1 + Fn, (n ≥ 0) Chứng minh đẳng thức: Fk = F2n4 Lời giải. S =Xn k=0 n k Để ý rằng: (−1)k.(−1)k = 1 nên ta có:  (−1)k n k = ∆ (−1)k−1 n − 1 k − 1  h ∆ (−1)kFki= (−1)k+1Fk+1 − (−1)kFk = (−1)k+1Fk+2 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 51 Áp dụng SPTP 3.2 cho S, ta được S =Xn k=0 n k Fk n − 1 n+1 n − 1 = (−1)k−1 k − 1 (−1)kFk k=0 −Xn k=0 (−1)k k (−1)k+1Fk+2 = nX−1 k=0 n − 1 k Fk+2 = S1 Hoàn toàn tương tự áp dụng SPTP 3.2 cho S1, ta được S1 = nX−1 n − 1 k Fk+2 k=0 = (−1)k−1 n − 2 k − 1 (−1)kFk+2 nk=0−nX−1 (−1)k n − 2 k (−1)k+1Fk+4 = nX−2 k=0 n − 2 k Fk+4 k=0 = S2 Sau n bước áp dụng SPTP 3.2, cuối cùng ta thu được: S = S1 = ... = Sn = nX−n k=0 n − n k Fk+2n = F2n Ví dụ 3.7 (dark templar). Tính tổng: n S =Xn k(−1)k k k=1 k2 + 3k + 2 4 Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 52 3.3. Một số bài toán và Ví dụ minh hoạ Lời giải. Ta viết lại tổng đã cho dưới dạng: k(−1)k n k(−1)k n + 2 S =Xn k=0 (k + 1)(k + 2) =Xn k k=0 k + 2 (n + 1)(n + 2) Do đó ta có: (−1)k n + 2 k + 2 = ∆ (−1)k−1 n + 1 k + 1  ∆(k) = k + 1 − k = 1 Áp dụng SPTP 3.2, ta được (n + 1)(n + 2)S =Xn k(−1)k n + 2 k + 2 k=0 = (−1)k−1 n + 1 k + 1 k n+1 k=0 −Xn k=0 (−1)k n + 1 k + 2 = nX−1 (−1)k n + 1 k + 2 = k=0 nX−1 k=0 ∆ (−1)k−1 n k + 1 = (−1)k−1 = −n n k + 1 nk=0 Từ đó ta có: S =−n (n + 1)(n + 2) Ví dụ 3.8. Chứng minh rằng: Xn k=0 n cos(x + 2k) = 2ncosn(1) cos(x + n) k 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 53 Lời giải. Một cách quen thuộc, ta phân tích:  (−1)k n k = ∆ (−1)k−1 n − 1 k − 1  h (−1)kcos(x + 2k)i= (−1)k+1 cos(x + 2 + 2k) − (−1)kcos(x + 2k) ∆ = (−1)k+12 cos(1) cos(x + 1 + 2k) Áp dụng SPTP 3.2, ta được S(n,x) =Xn n k cos(x + 2k) k=0 = (−1)k−1 n − 1 k − 1 cos(x + 2k) n+1 −Xn (−1)k n − 1 k k=0 (−1)k+12 cos(1) cos(x + 1 + 2k) k=0 = 2 cos(1) nX−1 k=0 n − 1 k cos(x + 1 + 2k) = 2 cos(1)S(n−1,x+1) Do đó: S(n,x) = 2 cos(1)S(n−1,x+1) = 22cos2(1)S(n−2,x+2) = ... = 2ncosn(1)S(0,x+n) = 2ncosn(1) cos(x + n) Ví dụ 3.9. Với các số nguyên dương m, n Đặt: Chứng minh rằng: S(m,n) =Xn k=0 2n−k m + k k S(m,n) =Xn k=0 m + n + 1 m + 1 + k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 54 3.3. Một số bài toán và Ví dụ minh hoạ Từ kết quả đó, chứng minh: S(m,n) + S(n,m) = 2m+n+1 4 Nhận xét. Bài toán này là sự kết hợp giữa các phép biến đổi tổng đại số và áp dụng SPTP 3.2. Lời giải. • Từ đề bài ta có: (đảo chiều lấy tổng) S(m,n) =Xn k=0 2k m + n − k n − k =Xn k=0 2k m + n − k m Phân tích sai phân:  m + n − k m = m + n + 1 − k m + 1 − m + n − k m + 1  ∆(2k) = 2k = −∆ m + n + 1 − k m + 1 Áp dụng SPTP 3.2, ta được m + n + 1 − k n+1 +Xn m + n − k S(m,n) = −2k m + 1 k=0 2k k=0 m + 1 = m + n + 1 m + 1 m + n + 1 + nX−1 k=0 2k m + n − k m + 1 = m + 1 + S(m,n,1) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 55 Áp dụng SPTP 3.2 hoàn toàn tương tự cho tổng S(m,n,1) S(m,n,1) = −2k m + n + 1 − k m + 2 nk=0+nX−1 2k m + n − k m + 2 = m + n + 1 m + 2 m + n + 1 + nX−2 k=0 2k k=0 m + n − k m + 2 = m + 2 + S(m,n,2) ...Thực hiện liên tiếp quá trình trên đến khi S(m,n,n−1) = m + n + 1 m + n m + n + 1 + nX−n k=0 2k m + n − k m + n = m + n + m + n + 1 m + n + 1 Từ các đẳng thức trên, suy ra: S(m,n) = m + n + 1 m + 1 + m + n + 1 m + 2 + ... + m + n + 1 m + n + 1 =Xn k=0 m + n + 1 m + 1 + k Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 56 3.3. Một số bài toán và Ví dụ minh hoạ • Như vậy ta có: S(m,n) + S(n,m) =Xn k=0 =Xn k=0 m + n + 1 m + 1 + k m + n + 1 n − k +Xm k=0 +Xm k=0 m + n + 1 n + 1 + k m + n + 1 n + 1 + k (Đối xứng) =Xn k=0 m + n + 1 k + +n+1 mX k=n+1 m + n + 1 k (Đảo chiều) (Tịnh tiến n + 1) = +n+1 mX k=0 m + n + 1 k (Gộp lại) = 2m+n+1 Qua những ví dụ trên chắc hẳn các bạn đã được thấy việc áp dụng linh hoạt phương pháp SPTP có hiệu quả mạnh như thế nào. SPTP sẽ biến đổi được từ một tổng tổ hợp phức tạp trở thành một tổng đơn giản hơn và đương nhiên cũng dễ tính toán và tìm ra kết quả hơn. Bên cạnh việc tính toán thông thường, một số bài toán ta có thể dễ dàng tìm được dạng khái quát hơn từ đề bài, khi quan sát được sự thay đổi của tổng mới sau một bước áp dụng SPTP. Sau đây là một số bài toán khó, được áp dụng phương pháp SPTP 3.2 để giải. Bài toán 3.1. Tính tổng: 2n (−1)k 4n S =X k=0 2n k 2k 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 57 Nhận xét. Đối với bài toán này ta rất khó đoán biết được đâu sẽ là ∆f(k) đâu sẽ là g(k) trong biểu thức lấy tổng. Trong đa số trường hợp như vậy, ta phải tiếp cận bài toán bằng cách giả tính sai phân ∆f(k) trước! f(k) có thể là một thành phần (phức tạp nhất) hoặc toàn bộ biểu thức lấy tổng. Trong trường hợp này ta sẽ tính Sai phân của cả biểu thức lấy tổng. Lời giải. Ta có:  (−1)k 4n 2k  =(−1)k+1 4n 2k + 2 (−1)k 4n 2k ∆ 2n k 2n k + 1 − 2n k 4n 4n = (−1)k+1  (4n − 2k)(4n − 2k − 1)  (2k + 2)(2k + 1) 2k 2k   (−1)k+14n 4n 2k 2n − k k + 1 2n k + 2n k = (2k + 1) 2n k Như vậy là sau khi ta lấy sai phân của toàn bộ biểu thức lấy tổng ta được một biểu thức mới, “thừa ra” một nhân tử Nhưng nếu ta viết: −4n 2k + 1 2n  (−1)k 4n  S =X k=0 thì không ổn, vì sao? −2k − 1 4n∆ 2n k 2k  Vì khi áp dụng SPTP thì biểu thức trong dấu ∆ sẽ thay k bởi k + 1, Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 58 3.3. Một số bài toán và Ví dụ minh hoạ khi đó 2n k + 1 = 0 khi k = 2n và phân thức khi đó sẽ không xác định! Để tránh điều đó xảy ra ta cần phải tính tách riêng số hạng cuối. Ta có: 2Xn−1 −2k − 1  (−1)k 4n 2k   S = 1 + k=0 4n∆ 2n k Dễ dàng tính được ∆ −2k − 1 4n = −12n Bây giờ, áp dụng SPTP 3.2 thì ta được:  −2k − 1 (−1)k 4n 2k   2n 2Xn−1 −1 (−1)k+1 4n 2k + 2 S = 1 + 4n· 2n k − k=0 2n· 2n k + 1 4n+12n2Xn−1 4n−−1 = 1 +−4n − 1 k=0 (−1)k+1 4n 2k + 2 2n (−1)k 4n k=0 2n k + 1 =12nX k=1 2n k 2k (Tịnh tiến 1) =12n· S −12n(Thêm bớt số hạng k = 0) Từ đó suy ra S =−1 2n − 1 Bài toán 3.2. Chứng minh đẳng thức: Xn k=0 2k k 2n − 2k n − k = 4n 4 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 59 Nhận xét. Bài này ta không thể đem cả biểu thức lấy tổng mà sai phân được, khi đó tổng thu được còn phức tạp hơn nhiều! Điều tương tự cũng xảy ra khi ta đem sai phân các thành phần. Vậy ta phải làm thế nào? Ý tưởng là ta sẽ biến đổi đề bài để làm xuất hiện một biểu thức sai phân quen thuộc: (−1)k Lời giải. Để ý rằng: n k (2n)! = [1.3...(2n − 1)].[2.4...(2n)] = 2n.n!(2n − 1)!! (n > 0) Còn nếu n = 0 thì: 1 = 0! = (2.0)! = 20.0!(2.0 − 1)!! = (−1)!! Ta viết lại tổng đã cho dưới dạng: S =Xn k=0 2k k 2n − 2k n − k =Xn k=0 =Xn k=0 =Xn k=0 (2n)!(2n − 2k)! k!k!(n − k)!(n − k)! 2n.n!(2n − 1)!!2n−k.(n − k)!(2n − 2k − 1)!! k!k!(n − k)!(n − k)! 2n(2k − 1)!!(2n − 2k − 1)!!n! k!(n − k)!n! =2n n! =2n Xn k=0 n k (2k − 1)!!(2n − 2k − 1)!! n!A Với tổng: A =Xn k=0 n k (2k − 1)!!(2n − 2k − 1)!! Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 60 3.3. Một số bài toán và Ví dụ minh hoạ Ta có:  (–1)k n k = ∆ (–1)k−1 n − 1 k − 1  h (–1)k(2k–1)!!(2n– 2k– 1)!!i= (2n)(–1)k+1(2k– 1)!!(2n– 2k– 3)!! ∆ Áp dụng SPTP 3.2 cho A, ta được: A = (−1)k−1 n − 1 k − 1 (−1)k(2k − 1)!!(2n − 2k − 1)!! n+1 −Xn (−1)k n − 1 k k=0 (2n)(−1)k+1(2k − 1)!!(2n − 2k − 3)!! k=0 n − 1 = (2n) nX−1 k=0 (2k − 1)!!(2n − 2k − 3)!! k = (2n)A1 Tương tự:  (−1)k n − 1 k = ∆ (−1)k−1 n − 2 k − 1  h ∆ (−1)k(2k − 1)!!(2n − 2k − 3)!!i= = (2n − 2)(−1)k+1(2k − 1)!!(2n − 2k − 5)!! Áp dụng SPTP 3.2 cho A1, ta được: A1 = (−1)k−1 n − 2 k − 1 (−1)k(2k − 1)!!(2n − 2k − 3)!! nk=0 − nX−1 (−1)k n − 2 k (2n − 2)(−1)k+1(2k − 1)!!(2n − 2k − 5)!! k=0 = (2n − 2) nX−2 k=0 n − 2 k (2k − 1)!!(2n − 2k − 5)!! = (2n − 2)A2 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 61 ...Tiếp tục quá trình trên cho đến khi, ta được: An = nX−n k=0 n − n k (2k − 1)!!(2n − 2k − (2n + 1))!! = 1 Từ các đẳng thức trên suy ra: A = (2n)(2n − 2)...2.An = 2n.n! Vậy ta có: S =2n n!· A = 4n Bài toán 3.3. Với các số tự nhiên m, n thoả mãn n ≥ m Chứng minh rằng: Xm =22m.n(n + m − 1)! (2m)!(n − m)! 4 k=0 Lời giải. 2n 2k n − k m − k Tư tưởng bài này hoàn toàn tương tự bài toán trên. Ta phân tích đề bài dưới dạng: S =Xm k=0 2n 2k n − k m − k =Xm k=0 =Xm k=0 (2n)!(n − k)! (2k)!(2n − 2k)!(n − m)!(m − k)! (2n)!(n − k)!m! 2k.k!(2k − 1)!!2n−k.(n − k)!(2n − 2k − 1)!!(n − m)!(m − k)!m! =(2n)! Xm m k 2n.m!(n − m)! =(2n)! k=0 (2k − 1)!!(2n − 2k − 1)!! 2n.m!(n − m)! · A Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 62 3.3. Một số bài toán và Ví dụ minh hoạ Xét tổng: A =Xm m k (2k − 1)!!(2n − 2k − 1)!! Ta có: k=0  (−1)k m k = ∆ (−1)k−1 m − 1 k − 1 ∆  (−1)k (2k − 1)!!(2n − 2k − 1)!!=(−1)k+1 = (2k + 1)!!(2n − 2k − 3)!! −(−1)k (2k − 1)!!(2n − 2k − 1)!! =(−1)k+1(2n) (2k + 1)!!(2n − 2k − 1)!! Áp dụng SPTP 3.2 cho A, ta được: A = (−1)k−1 m − 1 k − 1 ·(−1)k (2k − 1)!!(2n − 2k − 1)!! m+1 −Xm (−1)k m − 1 k ·(−1)k+1(2n) k=0 k=0 (2k + 1)!!(2n − 2k − 1)!! = (2n) mX−1 m − 1 k k=0 = (2n)A1 (2k + 1)!!(2n − 2k − 1)!! Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 63 Tương tự  (−1)k m − 1 k = ∆ (−1)k−1 m − 2 k − 1 ∆ (−1)k (2k + 1)!!(2n − 2k − 1)!! =  (2k + 3)!!(2n − 2k − 3)!! −(−1)k =(−1)k+1 =(−1)k+1(2n + 2) (2k + 3)!!(2n − 2k − 1)!! Áp dụng SPTP 3.2 cho A1, ta được: (2k + 1)!!(2n − 2k − 1)!! A1 = (−1)k−1 m − 2 k − 1 ·(−1)k (2k + 1)!!(2n − 2k − 1)!! mk=0 − mX−1 (−1)k m − 2 k ·(−1)k+1(2n + 2) (2k + 3)!!(2n − 2k − 1)!! k=0 = (2n + 2) mX−2 m − 2 k k=0 = (2n + 2)A2 (2k + 3)!!(2n − 2k − 1)!! ...Tiếp tục quá trình trên cho đến khi, ta được: m − m Am = mX−m k=0 (2k + 2m − 1)!!(2n − 2k − 1)!! =1 k (2m − 1)!!(2n − 1)!! Từ các đẳng thức trên suy ra: A = (2n)(2n + 2)...(2n + 2m − 2).Am =2m.n(n + 1)...(n + m − 1) (2m − 1)!!(2n − 1)!! Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 64 3.3. Một số bài toán và Ví dụ minh hoạ Vậy ta có: 2n.m!(n − m)! · A =(2n)!2m.n(n + 1)...(n + m − 1) S =(2n)! =22m.n(n + m − 1)! 2n.m!(n − m)!(2m − 1)!!(2n − 1)!! (2m)!(n − m)! Bài toán 3.4. Chứng minh đẳng thức: Xn n k 2 2n =24n(n!)4 k=0 (2k + 1) 2k (2n)!(2n + 1)! 4 Nhận xét. Đây là một bài toán rất khó! Tưởng như ngoài cách giải bằng hàm sinh và kiến thức về chuỗi hàm luỹ thừa, thì không có một phương pháp sơ cấp nào có thể tiếp cận được bài này! Tác giả đã khá “may mắn” khi tìm được một lời giải bằng SPTP 3.2 sau đây: Lời giải. Trước hết ta đưa tổng cần tính về dạng: Xn n k 2 =Xn n k n!(2k)!(2n − 2k)! k=0 (2k + 1) 2n k=0 k!(n − k)!(2n)!(2k + 1) 2k =Xn k=0 n k n!2kk!(2k–1)!!2n−k(n–k)!(2n–2k–1)!! k!(n–k)!(2n)!(2k + 1) =2n.n! (2n)! Xn k=0 n k (2k − 1)!!(2n − 2k − 1)!! 2k + 1 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 65 Như vậy đẳng thức cần chứng minh tương đương với: (2k − 1)!!(2n − 2k − 1)!! 2k + 1=23n.(n!)3 (2n + 1)! Ta có: S =Xn k=0 n k ∆ n − 1 k − 1 (2k − 3)!!(2n − 2k + 1)!! = = n − 1 k (2k − 1)!!(2n − 2k − 1)!! − n − 1 k − 1 (2k − 3)!!(2n − 2k + 1)!! = − n k (2k − 3)!!(2n − 2k − 1)!! Như vậy thừa số còn “sót” lại là −2k − 1 2k + 1 với: ∆ −2k − 1 2k + 1 = −2k + 1 2k + 3+2k − 1 2k + 1= −4 (2k + 1)(2k + 3) Áp dụng SPTP 3.2, ta được: S =Xn k=0 n k (2k − 1)!!(2n − 2k − 1)!! 2k + 1 = n − 1 k − 1 (2k − 3)!!(2n − 2k + 1)!! −2k − 1 2k + 1 n+1 k=0 −Xn n − 1 k (2k − 1)!!(2n − 2k − 1)!!(−4) k=0 n − 1 (2k + 1)(2k + 3) = nX−1 k=0 4 (2k − 1)!!(2n − 2k − 1)!! k (2k + 1)(2k + 3) Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 66 3.3. Một số bài toán và Ví dụ minh hoạ Quan sát sự thay đổi của tổng thu được, sau một lần áp dụng SPTP, ta nhận thấy dạng tổng quát của tổng cần tính là: nX−p [(2p)!!]2 n − p k (2k − 1)!!(2n − 2k − 1)!! S(p,n) = (2k + 1 + 2j) Thật vậy: k=0 (2p − 1)!! Qp j=0 ∆ n − p − 1 k − 1 (2k − 3 − 2p)!!(2n − 2k + 1)!! = = n − p − 1 k (2k − 1 − 2p)!!(2n − 2k − 1)!! − n − p − 1 k − 1 (2k − 3 − 2p)!!(2n − 2k + 1)!! = (2k − 3 − 2p)!!(2n − 2k − 1)!! n − p − 1 k (2k − 1 − 2p) n − p − n − p − 1 k − 1 (2n − 2k + 1) = −(2p + 1) Còn lại:  (2k − 3 − 2p)!!(2n − 2k − 1)!! k  ∆ Yp j=0 2k − 1 − 2j 2k + 1 + 2j  =Yp j=0 2k + 3 + 2j−Yp 2k + 1 − 2j j=0 2k − 1 − 2j 2k + 1 + 2j = (2p + 2)2pQ−1 j=0 (2k − 1 − 2j) pQ+1 j=0 (2k + 1 + 2j) Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.3. Một số bài toán và Ví dụ minh hoạ 67 Áp dụng SPTP 3.2, ta được: S(n,p) =  −[(2p)!!]2 n − p − 1 k − 1 (2p − 1)!!(2p + 1) (2k − 3 − 2p)!!(2n − 2k + 1)!!  ·Yp 2k − 1 − 2j  n−p+1 n − p − 1 j=0 2k + 1 + 2j k=0 nX−p "[(2p)!!]2(−1) (2k − 1 − 2p)!!(2n − 2k − 1)!! k − k=0 (2p − 1)!!(2p + 1) (2p + 2)2pQ−1 (2k − 1 − 2j)   n − p − 1 · pQ+1 j=0 j=0 (2k + 1 + 2j) n−Xp−1 [(2p + 2)!!]2 (2k − 1)!!(2n − 2k − 1)!! k = k=0 (2p + 1)!!pQ+1 j=0 (2k + 1 + 2j) = S(p+1,n) Từ đó suy ra: S = S(0,n) = S(1,n) = ... = S(n,n) = nX−n [(2n)!!]2 n − n k (2k − 1)!!(2n − 2k − 1)!! = k=0 (2n − 1)!! Qn j=0 (2k + 1 + 2j) =[(2n)!!]2 (2n + 1)!! =[(2n)!!]3 (2n + 1)!!(2n)!! =23n(n!)3 (2n + 1)! Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 68 3.4. Bài tập tự luyện Nhận xét. Luyện tập sử dụng phương pháp Sai Phân Từng Phần giúp cho bạn có nhiều kỹ năng biến đổi Đại Số và mỗi khi nhìn thấy biểu thức tổng bạn sẽ tự tin và đỡ choáng ngợp hơn! Bên cạnh đó SPTP cũng như tương tự như Tích Phân Từng Phần vậy, đều có những ưu nhược điểm của nó! Nếu không tinh ý, bạn dễ rơi vào vòng “luẩn quẩn” của tổng sau khi lấy SPTP, hoặc sau khi lấy SPTP tổng thu được còn khó hơn! Nhược điểm lớn nhất của phương pháp này là bạn phải “nhìn thấy” được Sai Phân trong biểu thức lấy tổng đã cho, giống như kiểu bạn phải tìm được nguyên hàm của v(x) để cho d(V (x)) = v(x)dx sau đó mới áp dụng được công thức Tích Phân Từng Phần. Việc làm này không phải lúc nào cũng thực hiện được! Để kết thúc phần này, mời các bạn cùng luyện tập với các bài tập sau: 3.4 Bài tập tự luyện Bài 1. Cho n là số nguyên dương. Chứng minh đẳng thức: Xn (−1)k n k 2n −1 Bài 2. Tính tổng: k=0 n + k= n n n S =Xn (−1)k k k=0 Bài 3. (dark templar) Tính tổng: (k + 1)(k + 3) S =Xn (−1)k n k k=0 4k2 − 1 Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp 3.4. Bài tập tự luyện 69 Bài 4. Tính tổng: Xn k=0 (−1)k n k (2k2 + 5k + 2) k + 3 Bài 5. Chứng minh đẳng thức: n Xn (−1)k (2k + 1)(2k + 3) =4n k k=0 (2n + 3) 2n + 1 n Bài 6. Tính tổng: S =Xn k=0 (−1)k(n − k) 2n k Bài 7. Tính tổng: S =Xn k=0 2n n + k 2k2 + k n + k + 1 Bài 8. Tính tổng: 2n S =X k=0 (−2)k 2n + k 2k Bài 9. Với số nguyên dương n và số thực α. Tính tổng: S =Xn k=0 Bài 10. Chứng minh đẳng thức: (−1)k k + α n k 2n X k=0 −12 k 2kk 2n + 1 k + 1 =(2n + 1)!! (2n)!! Chuyên đề Đẳng Thức Tổ Hợp N Diễn đàn Toán học 70 3.4. Bài tập tự luyện Bài 11. Chứng minh đẳng thức 2n X k=0 (−1)k 2k k 4n − 2k 2n − k = 22n 2n n Bài 12. Tính tổng: Xn k=0 n k sin(x + 2k) Bài 13. Chứng minh đẳng thức: 2n X k=0 2n k cos[2(n − k)x] = 4ncos2n(x) Bài 14. Cho dãy Fibonacci ( F0 = 0; F1 = 1 Fn+2 = Fn+1 + Fn (n ≥ 0) Chứng minh đẳng thức: Xn k=0 n k F3k = 2nF2n Diễn đàn Toán học N Chuyên đề Đẳng Thức Tổ Hợp