欲证明容斥原理，我们首先要验证以下的关于指示函数的等式：
1
∪
i
=
1
n
A
i
=
∑
k
=
1
n
(
−
1
)
k
−
1
∑
I
⊂
{
1
,
…
,
n
}
|
I
|
=
k
1
A
I
(
∗
)
{\displaystyle 1_{\cup _{i=1}^{n}A_{i}}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}1_{A_{I}}\qquad (*)}
至少有两种方法来证明这个等式：
第一种方法 我们只需证明对于A1，……，An的并集中的每一个x，等式都成立。假设x正好属于m个集合（1 ≤ m ≤ n），不妨设它们为A1，……，Am。则x处的等式化为：
1
=
∑
k
=
1
m
(
−
1
)
k
−
1
∑
I
⊂
{
1
,
…
,
m
}
|
I
|
=
k
1.
{\displaystyle 1=\sum _{k=1}^{m}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,m\} \atop \scriptstyle |I|=k}1.}
m元素集合中的k元素子集的个数，是二项式系数
(
m
k
)
{\displaystyle \textstyle {\binom {m}{k}}}
的组合解释。由于
1
=
(
m
0
)
{\displaystyle \textstyle 1={\binom {m}{0}}}
，我们有：
(
m
0
)
=
∑
k
=
1
m
(
−
1
)
k
−
1
(
m
k
)
.
{\displaystyle {\binom {m}{0}}=\sum _{k=1}^{m}(-1)^{k-1}{\binom {m}{k}}.}
把所有的项移到等式的左端，我们便得到(1 – 1)m的二项式展开式，因此可以看出，(*)对x成立。
第二种方法 设A表示集合A1，……，An的并集。于是：
0
=
(
1
A
−
1
A
1
)
(
1
A
−
1
A
2
)
⋯
(
1
A
−
1
A
n
)
,
{\displaystyle 0=(1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,,}
这是因为对于不在A内的x，两边都等于零，而如果x属于其中一个集合，例如Am，则对应的第m个因子为零。把右端的乘积展开来，便可得到等式(*)。
归纳法证明
编辑
设
S
1
=
n
(
A
1
)
+
n
(
A
2
)
+
n
(
A
3
)
+
⋯
+
n
(
A
n
)
{\displaystyle S_{1}=n(A_{1})+n(A_{2})+n(A_{3})+\cdots +n(A_{n})}
S
2
=
n
(
A
1
∩
A
2
)
+
n
(
A
1
∩
A
3
)
+
⋯
+
n
(
A
1
∩
A
n
)
+
n
(
A
2
∩
A
3
)
+
⋯
+
n
(
A
n
−
1
∩
A
n
)
{\displaystyle S_{2}=n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{1}\cap A_{n})\;+\;n(A_{2}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n})}
S
3
=
n
(
A
1
∩
A
2
∩
A
3
)
+
⋯
+
n
(
A
n
−
2
∩
A
n
−
1
∩
A
n
)
{\displaystyle S_{3}=n(A_{1}\cap A_{2}\cap A_{3})+\cdots +n(A_{n-2}\cap A_{n-1}\cap A_{n})}
⋮
S
n
=
n
(
A
1
∩
A
2
∩
A
3
∩
⋯
∩
A
n
)
{\displaystyle S_{n}=n(A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n})}
求证
n
(
A
1
∪
A
2
∪
A
3
∪
⋯
∪
A
n
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
n
−
1
S
n
.
{\displaystyle n(A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{n-1}S_{n}.}
证明：
当
n
=
2
{\displaystyle n=2}
时，
n
(
A
1
∪
A
2
)
=
n
(
A
1
)
+
n
(
A
2
)
−
n
(
A
1
∩
A
2
)
=
S
1
−
S
2
.
{\displaystyle n(A_{1}\cup A_{2})=n(A_{1})+n(A_{2})-n(A_{1}\cap A_{2})=S_{1}-S_{2}.}
假设当
n
=
k
(
k
≥
2
)
{\displaystyle n=k\ (k\geq 2)}
时，有
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
k
−
1
S
k
.
{\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k-1}S_{k}.}
当
n
=
k
+
1
{\displaystyle n=k+1}
时，
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
∪
A
k
+
1
)
=
n
(
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
∪
A
k
+
1
)
=
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
+
n
(
A
k
+
1
)
−
n
(
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
∩
A
k
+
1
)
=
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
)
+
n
(
A
k
+
1
)
−
n
(
(
A
1
∩
A
k
+
1
)
∪
(
A
2
∩
A
k
+
1
)
∪
⋯
∪
(
A
k
∩
A
k
+
1
)
)
.
{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{k}\cup A_{k+1})&=n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cup A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cap A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cap A_{k+1})\cup (A_{2}\cap A_{k+1})\cup \cdots \cup (A_{k}\cap A_{k+1}){\Bigr )}.\end{aligned}}}
∵ 当 \(n=k\) 时，上式成立，
∴
n
(
A
1
∪
A
2
∪
⋯
∪
A
k
+
1
)
=
S
1
−
S
2
+
S
3
−
⋯
+
(
−
1
)
k
S
k
+
1
.
{\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k+1})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k}S_{k+1}.}
综上所述，当
n
≥
2
{\displaystyle n\geq 2}
时，
n
(
A
1
∪
A
2
∪
⋯
∪
A
n
)
=
n
(
A
1
)
+
n
(
A
2
)
+
⋯
+
n
(
A
n
)
−
[
n
(
A
1
∩
A
2
)
+
n
(
A
1
∩
A
3
)
+
⋯
+
n
(
A
n
−
1
∩
A
n
)
]
+
[
n
(
A
1
∩
A
2
∩
A
3
)
+
⋯
]
−
⋯
+
(
−
1
)
n
−
1
n
(
A
1
∩
A
2
∩
⋯
∩
A
n
)
.
{\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{n})=&\;n(A_{1})+n(A_{2})+\cdots +n(A_{n})\\[1ex]&\;-{\Bigl [}n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n}){\Bigr ]}\\[1ex]&\;+{\Bigl [}n(A_{1}\cap A_{2}\cap A_{3})+\cdots {\Bigr ]}\\[1ex]&\;-\cdots +(-1)^{n-1}n(A_{1}\cap A_{2}\cap \cdots \cap A_{n}).\end{aligned}}}