Có tất cả $4^n$ cặp tập con $(A,B)$ của XChúng ta tiếp tục với bài toán sau:
Problem 2: Cho tập hợp $X$ gồm $n$ phần tử. Với mỗi cặp tập con $A_{1}$, $A_{2}$ của $X$ ta tính được số phần tử của $A_{1}\cap{A_{2}}$. Chứng minh rằng tất cả các số nhận được bằng $n4^{n-1}$
Ta chia các tập con này thành các bộ $4$: $(A \cap B,\bar{A} \cap B,A \cap \bar{B},\bar{A}\cap \bar{B})$, có $4^{n-1}$ bộ như vậy
Khi đó mỗi phần tử $a\in X$ chỉ thuộc 1 trong trong 4 cặp thuộc 1 bộ mà có n phần tử
$\Rightarrow \sum A\cap B= n.4^{n-1}$
- perfectstrong và Trần Đức Anh @@ thích