(n+1)m = nm + C(m,1)nm-1 + C(m,2)nm-2 + ... + C(m,m-1)n + 1
這裡
C(m,k) = m!/k!/(m-k)!
1m = 1
2m = 1m + C(m,1)2m-1 + C(m,2)2m-2 + ... + C(m,m-1)2 + 1
...
(n+1)m = nm + C(m,1)nm-1 + C(m,2)nm-2 + ... + C(m,m-1)n + 1
所以, 將上面 n+1個式子左右分別相加, 消去左右相同的項,
(n+1)m -1 = C(m,1)Sm-1 + C(m,2)Sm-2 + ... + C(m,m-1)S1 + n
C(m,1)Sm-1 = (n+1)m -(n+1) - C(m,2)Sm-2 - ... - C(m,m-1)S1
例如, 當 m = 4,
C(4,1) = 4, C(4,2)=6, C(4,3)=4
4S3 = (n+1)4 -(n+1) -6S2 - 4S1