note[7]

自己瞎推了一个式子，然后打表发现前几项是 $2^{n-1}$ 。

然后改了一改得到这样的式子。

$$f_0 = 1, ~f_n = \sum_{0 \le i < n} f_i$$

通项为 $f_n = 2^n$ 。然后就试图找到这个式子的意义。

实际上这个东西的一种意义是 $n$ 元集的子集个数

证明：这个递推式就是在枚举每个集合的最大元素。$\square$

（QAQ.jpg