f(x)＝Π[i＝1〜n](x^1＋x^2＋…＋x^ki)＝Σ[a∈A]x^(a1＋a2＋…＋an)とおく。ただし
A＝{a：{1,2,…,n}→N｜1≦ai≦ki for i＝1〜n}とおいた。これをさらに変形して、
Σ[a∈A]x^(a1＋a2＋…＋an)＝Σ[r＝0〜d−1]Σ[a∈A, a1＋…＋an≡r (mod d)]x^(a1＋a2＋…＋an)
＝Σ[r＝0〜d−1]Tr(x)とする。ただしTr(x)＝Σ[a∈A, a1＋…＋an≡r (mod d)]x^(a1＋a2＋…＋an)と
おいた。ω＝e^(2πi/d)とするとき、k∈Zに対してTr(ω^k)＝Σ[a∈A, a1＋…＋an≡r (mod d)]ω^{k(a1＋a2＋…＋an)}
＝Σ[a∈A, a1＋…＋an≡r (mod d)]ω^{kr}＝ω^(kr)Pr となる。ただしPr＝Σ[a∈A, a1＋…＋an≡r (mod d)]1
＝「a1＋…＋an≡r (mod d)が成り立つa∈Aの個数」とおいた。このとき
f(ω^k)＝Σ[r＝0〜d−1]Tr(ω^k)＝Σ[r＝0〜d−1]ω^(kr)Pr　…＊
となるので、k＝0,1,…,d−1を＊に代入し、得られたd個の式を全て足し合わせることでΣ[k＝0〜d−1]f(ω^k)＝dP0と
なるので、P0＝Σ[k＝0〜d−1]f(ω^k)/dとなる。P0＝「a1＋…＋an≡0 (mod d)が成り立つa∈Aの個数」であり、これが
求める個数であった。以上より、Σ[k＝0〜d−1]f(ω^k)/d が答えとなる。