$\displaystyle \dfrac{1}{(1 - x) ^ {k + 1}} = \sum _ {i = 0} ^ \infty \binom{i + k}{k} x ^ i$ を思い出すと、$\displaystyle \sum _ {i = 0} ^ \infty i ^ d (rx) ^ i = \dfrac{f}{(1 - rx) ^ {d + 1}}$ なる高々 $d$ 次の $f$ が存在することが分かる。いま計算したいのは $[x ^ {n - 1}] \dfrac{f}{(1 - x)(1 - rx) ^ {d + 1}}$ である。
左辺の $d + 1$ 次の項の係数の計算に関しては、$\dfrac{f}{(1 - x)(1 - rx) ^ {d + 1}}$ の $d + 1$ 次以下の項は実際に $\displaystyle \sum _ {i = 0} ^ j i ^ d r ^ i$ を計算することで得られ、$(1 - rx) ^ {d + 1}$ に関しては二項定理で展開すればよいので、$O(d)$ 時間。
右辺の $d + 1$ 次の項の係数の計算に関しても、$\dfrac{1}{1 - x}$ を掛けることが累積和を取る操作と対応しているため $(1 - rx) ^ {d + 1}$ を同様に二項定理で展開することで $O(d)$ 時間。
以上で定数 $c$ を $O(d)$ 時間で得ることができた。また、これにより $\dfrac{g}{(1 - rx) ^ {d + 1}} = \dfrac{f}{(1 - x)(1 - rx) ^ {d + 1}} - \dfrac{c}{1 - x}$ の $d + 1$ 次以下の係数を求めることができる。
即ち、$\displaystyle h(x) = \sum _ {j = 0} ^ d \dfrac{g _ j}{r ^ j \cdot d!} \prod _ {k = 1} ^ d (x - j + k)$ とおくと、$[x ^ i] \dfrac{g}{(1 - rx) ^ {d + 1}} = r ^ i \cdot h(i)$ が成り立つ。いま $h(0),\ldots,h(d)$ の値は既知であるから、ラグランジュの補間公式により $h(n - 1)$ を $O(d)$ 時間で計算することができる。計算すべき値は $[x ^ {n - 1}] \dfrac{f}{(1 - x)(1 - rx) ^ {d + 1}} = c + r ^ {n - 1} h(n - 1)$ であるから、結局全体 $O(d + \log n)$ 時間で $\displaystyle \sum _ {i = 0} ^ {n - 1} i ^ d r ^ i$ を計算することができた。