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