{1,…,m−1}\{1,\ldots,m-1\}{1,…,m−1} 上の組について、各 AiA_iAi に mmm を含めるか独立に選ぶ。拡張は 2n2^n2n 個あり、古い和の寄与は 2n2^n2n 倍、mmm を含むものは一つを除いて全てなので第2項を得る。従って s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)s(n,m)=2^ns(n,m-1)+(2^n-1)2^{n(m-1)}s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)。