Polynomial Multiplication

Note that when you multiply two polynomials together, their coefficients are convolved. To see this, let $p(x)$ denote the $m$ th-order polynomial

$$p(x) = p_0 + p_1 x + p_2 x^2 + \cdots + p_m x^m$$

with coefficients $p_i$ , and let $q(x)$ denote the $n$ th-order polynomial

$$q(x) = q_0 + q_1 x + q_2 x^2 + \cdots + q_n x^n$$

with coefficients $q_i$ . Then we have [1]

$$\begin{eqnarray*} p(x) q(x) &=& p_0 q_0 + (p_0 q_1 + p_1 q_0) x + (p_0 q_2 + p_1 q_1 + p_2 q_0) x^2 \\ & & \mathop{+} (p_0 q_3 + p_1 q_2 + p_2 q_1 + p_3 q_0) x^3\\ & & \mathop{+} (p_0 q_4 + p_1 q_3 + p_2 q_2 + p_3 q_1 + p_4 q_0) x^4 + \cdots\\ & & \mathop{+} (p_0 q_{n+m} + p_1 q_{n+m-1} + p_2 q_{n+m-2} \\ & & \qquad\qquad\; \mathop{+} p_{n+m-1} q_1 + p_{n+m} q_0) x^{n+m}. \end{eqnarray*}$$

Denoting $p(x) q(x)$ by

$$r(x) \isdef p(x) q(x) = r_0 + r_1 x + r_2 x^2 + \cdots + r_{m+n} x^{m+n},$$

we have that the $i$ th coefficient can be expressed as

$$\begin{eqnarray*} r_i &=& p_0 q_i + p_1 q_{i-1} + p_2 q_{i-2} + \cdots + p_{i-1}q_1 + p_i q_0\\ &=& \sum_{j=0}^i p_j q_{i-j} = \sum_{j=-\infty}^\infty p_j q_{i-j}\\ &\isdef & (p \circledast q)(i), \end{eqnarray*}$$

where $p_i$ and $q_i$ are doubly infinite sequences, defined as zero for $i<0$ and $i>m,n$ , respectively.