Generic formula for polynomial expansion Short version: Is there a generic formula for a polynomial expansion of the form $\prod_i{(x-p_i)}$?
Long version: I need to verify finding the roots of polynomials (C++), and, while I could do it by simply evaluating at a point, or more, I'd like to have the polynomial expanded, to collect the terms. The $p_i$ terms are complex conjugate roots (all negative real part, if that matters), and if the order N is odd, there's an additional negative real root.
Currently, I am storing each root as a vector of 2 complex values (all inside another vector of length N), with the terms of $x-p_i$: $\left[[1, p_0], [1, p_1], ...\right]$. For expansion I am convolving the 1st with the 2nd, store the result in a length 3 vector, backup this vector in order to be reused for the next convolution, which needs to resize the vector, then repeat the process. This makes me cringe, but it works, eventually. However, I'd like to know if there's a more humane way of doing this.
 A: Yes: you can expand the whole thing at once using the $N$-ary distributive law, which says that an $N$-ary product of sums is the sum of all the $N$-ary products you can get from choosing one term from each of the sums.  This means that $\prod_{i=0}^{N-1}(x-p_i)$ expands as as sum of $2^N$ terms, one for each way to choose either $x$ or $-p_i$ from each factor.  Grouping the terms according to the power of $x$, this means that the coefficient of $x^k$ is the sum of all products of $N-k$ different choices of $-p_i$, also known as the $(N-k)$th elementary symmetric polynomial in the $-p_i$.  To be explicit, the expansion is $$\prod_{i=0}^{N-1}(x-p_i)=\sum_{k=0}^N(-1)^{N-k}\left(\sum_{0\leq i_1<i_2<\dots<i_{N-k}\leq N-1}\prod_{j=1}^{N-k}p_{i_j}\right)x^k$$ (the factor of $(-1)^{N-k}$ coming from pulling out the $-1$ from each $-p_{i_j}$).  For instance, when $N=4$, you get $$x^4-(p_0+p_1+p_2+p_3)x^3+(p_0p_1+p_0p_2+p_0p_3+p_1p_2+p_1p_3+p_2p_3)x^2-(p_0p_1p_2+p_0p_1p_3+p_0p_2p_3+p_1p_2p_3)x+p_0p_1p_2p_3.$$
I suspect, though, that your method of iteratively multiplying the factors one by one is more computationally efficient than trying to use this full expansion directly, since it should cut down on the number of separate multiplications you have to do (you don't want to have to separately multiply the $p_i$ together for each of $2^N$ different terms!).
