For the polynomial $$ p(x) = \sum_{i=0}^n c_i x^i, $$ of real coefficients and real variable, obtain the coefficient of $$ q(x) = \left(1 + x\right)^n p\left( \frac{a + b x}{1 + x} \right), $$ as efficiently as possible.
This problem arises when one try to implement the Vincent-Alesina-Galuzzi root-brackting algorithm. Ultimatly, the goal is to count the number of sign change in the coefficient of $q(x)$.
I found a few expressions for $q(x)$ \begin{align} q(x) &= \left(1+x\right)^n \sum_{i=0}^n c_i\left(\frac{a+b x}{1+x}\right)^i, \tag{1} \\ &= \sum_{i=0}^n c_i \left(a +b x\right)^i \left(1+x\right)^{n-i}, \tag{2} \\ &= \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^{n-i} c_i \binom{i}{j} a^{i-j} \left(b x \right)^{j} \binom{n-i}{k} x^{k} \tag{3} \end{align} but I don't see an efficient implementation for either (1), (2) or (3).
mathreadler mentionned convolution. I think this point to the Fourier transform that may simplify the inner sums in (3). But, I'm not sure if this is efficient.