Cho tập hợp $M$ gồm $n$ phần tử. Với 2 tập con $A;B$ tùy ý của $M$, tính số phần tử tập [tex]A\cap B[/tex].
Tính tổng của tất cả các số phần tử của mọi giao có thể gồm 2 tập con của $M$.
Bổ đề: Có $3^n$ cách chọn 2 tập con không giao nhau từ $1$ $n$-tập
Chứng minh: Chọn từ tập mẹ một tập con gồm $k$ phần tử có $C^k_n$ cách. Từ $n-k$ phần tử còn lại của tập mẹ ta chọn thêm một tập con nữa, có $2^{n-k}$ cách. Vậy ta có $\sum\limits_{k=0}^n C^k_n 2^{n-k}$ cách chọn như vậy
Ta có $$3^n = (2+1)^n = \sum_{k=0}^n C^k_n 2^{n-k}$$
Hoàn tất chứng minh.
Áp dụng: Từ tập $M$ ta chọn 1 tập con là $K$ có $k$ phần tử. Từ $n-k$ phần tử con lại ta lập thêm 2 tập con không giao nhau nữa là $A'$ và $B'$, thì ta có thể chọn $A = A' \cup K$ và $B = B' \cup K$. Do đó số cách chọn $A$, $B$ sao cho $A \cap B = K$ có $k$ phần tử là $C^k_n \cdot 3^{n-k}$, tổng số phần tử của các $k$-tập có thể lập ra là $k C^k_n \cdot 3^{n-k}$. Tóm lại ta cần tính tổng $$\sum_{k=0}^n k C^k_n 3^{n-k}$$
Xét $\displaystyle (3+x)^n = \sum\limits_{k=0}^n C^k_n 3^{n-k} x^k$
Đạo hàm hai vế thu được $n(3+x)^{n-1} = \sum\limits_{k=0}^n k C^k_n 3^{n-k} x^{k-1}$
Thay $x = 1$ ta suy ra $\sum\limits_{k=0}^n k C^k_n 3^{n-k} = n4^{n-1}$
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
