Fast Fourier Transform with Negative Integer Exponent

Question

Given $f(x)=ax+b+\frac{c}{x}$ and $N$, I'd like to ask how to calculate $\sum_{i=1}^{N}f(x)^i$ efficiently using fast Fourier transform?

Answer 1

Power series multiplication is convolution in terms of coefficients, but multiplication in Fourier transform domain of coefficients.

This is thanks to the Convolution Theorem, which can be written for example

$$(f * g)(t) = \mathcal F^{-1}(\mathcal F(f)\cdot \mathcal F(g))(t)$$

Answer 2

No need to FFT! Just write $$\sum_{i=1}^{N}f(x)^i=f(x){1-f^{N+1}(x)\over 1-f(x)}=\left(ax+b+\frac{c}{x}\right){1-\left(ax+b+\frac{c}{x}\right)^{N+1}\over 1-\left(ax+b+\frac{c}{x}\right)}$$