$$
\sum_{i=1}^n \frac{\binom n i(-1)^{i-1}}i=\sum_{i=1}^n \frac{1}{i}
$$
min-max 反演
考虑这样一个问题:
- 有一个可重集合,初始为空,每次从 $[1,n]$ 中等概率选择一个整数加入集合.
- 问期望操作多少次能使得 $[1,n]$ 中每个整数都在集合中.
设 $E(i)$ 表示集合中已经有 $i$ 种不同的整数,期望操作多少次能加入一个新的整数,易知 $E(i)=\frac {n} {n-i}$ .
这个问题的答案就是
$$
ans=\sum_{i=0}^{n-1} E(i)=n\cdot \sum_{i=1}^n \frac{1}{i}
$$
考虑用另一种方法求解这个问题,根据 min-max 反演可知
$$
ans=\sum_{i=1}^{n}\binom n i(-1)^{i-1}\cdot \frac{n}{i}
$$
于是可得
$$
\sum_{i=1}^n \frac{\binom n i(-1)^{i-1}}i=\sum_{i=1}^n \frac{1}{i}
$$
积分
构造一个函数
$$
f(x)=\frac{1-(1-x)^n}{x}
$$
考虑 $f(x)$ 在区间 $[0,1]$ 上的定积分 $s$ ,
$$
s=\int_0^1 \frac{1-(1-x)^n}{x} {\rm d}x
$$
用第一类换元法,令 $t=1-x$ ,可得
$$
\begin{aligned}
s&=\int_0^1\frac{1-t^n}{1-t} {\rm d}t \\
&=\int_0^1(\sum_{i=0}^{n-1}t^i){\rm d}t \\
&=\sum_{i=1}^n\frac 1 i
\end{aligned}
$$
若利用二项式定理直接进行积分,
$$
\begin{aligned}
s&=\int_0^1 \frac{1-(1-x)^n}{x} {\rm d}x \\
&=\int_0^1 \frac{1-\sum_{i=0}^n\binom n i(-1)^ix^i}{x} {\rm d}x\\
&=\int_0^1{\sum_{i=1}^n\binom n i (-1)^{i-1}x^{i-1}} {\rm d}x\\
&=\sum_{i=1}^n \frac{\binom n i(-1)^{i-1}}i
\end{aligned}
$$
于是可知
$$
\sum_{i=1}^n \frac{\binom n i(-1)^{i-1}}i=\sum_{i=1}^n \frac{1}{i}
$$