容斥原理

已知 $|A \cup B|=|A|+|B|-|A \cap B|$ $|A_1 \cup A_2 \cup ... \cup A_n|=(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k}| \ which\ b_i∈[1,n])$ 接下来是数学归纳部分 $|A_1 \cup A_2 \cup ... \cup A_n \cup A_{n+1}|=|(A_1 \cup A_2 \cup ... \cup A_n) \cup A_{n+1}|$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =|A_1 \cup A_2 \cup ... \cup A_n|+|A_{n+1}|-|(A_1 \cup A_2 \cup ... \cup A_n) \cap A_{n+1}|$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k}| \ which\ b_i∈[1,n])+|A_{n+1}|-|(A_1 \cap A_{n+1}) \cup (A_2 \cap A_{n+1}) \cup ... \cup (A_n \cap A_{n+1})|$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k}| \ which\ b_i∈[1,n])+|A_{n+1}|-(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k} \cap A_{n+1}| \ which\ b_i∈[1,n])$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k}| \ which\ b_i∈[1,n])+|A_{n+1}|+(\Sigma (-1)^{(k+1)-1}|A_{b_1} \cap ... \cap A_{b_k} \cap A_{n+1}| \ which\ b_i∈[1,n])$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(\Sigma (-1)^{k-1}|A_{b_1} \cap ... \cap A_{b_k}| \ which\ b_i∈[1,n+1])$