设：

Si(n)=∑j=0n−1jiS_i(n)=\sum_{j=0}^{n-1}j^i

对 Si+1(n)S_{i+1}(n) 使用扰动法，

Si+1(n)=∑j=0n−1ji+1=∑j=0nji+1−ni+1=∑j=1nji+1−ni+1=∑j=0n−1(j+1)i+1−ni+1=∑j=0n−1(j+1)i+1−ni+1=∑j=0n−1∑c=0i+1(i+1c)jc−ni+1=∑c=0i+1(i+1c)Sc(n)−ni+1=Si+1(n)+(i+1)Si(n)+∑c=0i−1(i+1c)Sc(n)−ni+1S_{i+1}(n)=\sum_{j=0}^{n-1}j^{i+1}\\ =\sum_{j=0}^{n}j^{i+1}-n^{i+1}\\ =\sum_{j=1}^nj^{i+1}-n^{i+1}\\ =\sum_{j=0}^{n-1}(j+1)^{i+1}-n^{i+1}\\ =\sum_{j=0}^{n-1}(j+1)^{i+1}-n^{i+1}\\ =\sum_{j=0}^{n-1}\sum_{c=0}^{i+1}\binom{i+1}{c}j^c-n^{i+1}\\ =\sum_{c=0}^{i+1}\binom{i+1}{c}S_c(n)-n^{i+1}\\ =S_{i+1}(n)+(i+1)S_i(n)+\sum_{c=0}^{i-1}\binom{i+1}{c}S_c(n)-n^{i+1}

__END__