ステップ2で数えた文字列を、2番目の 111 のすべての位置 k+1k+1k+1 について足すと、長さ (n+1)(n+1)(n+1) で r+1r+1r+1 個の 1 を含む各文字列をちょうど1回数えるので、合計は (n+1r+1)\binom{n+1}{r+1}(r+1n+1) となる。一方、項ごとに見ると、この和は ∑kk(n−kr−1)\sum_k k\binom{n-k}{r-1}∑kk(r−1n−k) と一致する。これはステップ1の和であり、(k1)=k\binom{k}{1}=k(1k)=k だからである。