# Fast Fourier Transform with Negative Integer Exponent

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?

• It works same way as with polynomials. Just place constant term in middle. – mathreadler Mar 17 at 18:34

$$(f * g)(t) = \mathcal F^{-1}(\mathcal F(f)\cdot \mathcal F(g))(t)$$
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)}$$