Coefficients of Polynomial Product

From ProofWiki
Jump to: navigation, search


Let $J$ be a set.

Let $p_1, \ldots p_n$ be polynomial forms in the indeterminates $\left\{{X_j : j \in J}\right\}$ over a commutative ring $R$.

Suppose that for each $i$ with $1 \le i \le n$, we have, for appropriate $a_{i,k} \in R$:

$p_i = \displaystyle \sum_{k \mathop \in Z} a_{i,k} X^k$

where $Z$ comprises the multiindices of natural numbers over $J$.


$\displaystyle \prod_{i \mathop = 1}^n p_i = \displaystyle \sum_{k \mathop \in Z} b_k X^k$


$\displaystyle b_k := \sum_{k_1 + \cdots + k_n \mathop = k} \left({\prod_{i \mathop = 1}^n a_{i, k_i} }\right)$


We proceed by induction over $n \ge 1$.

Base case

If $n = 1$ the result is trivially true.

This establishes the base case.

Induction Hypothesis

This is our induction hypothesis:

$\displaystyle \prod_{i \mathop = 1}^{n-1} p_i = \displaystyle \sum_{k \mathop \in Z} c_d X^k$


$\displaystyle c_d := \sum_{k_1 + \cdots + k_{n-1} = d} \left({\prod_{i \mathop = 1}^{n-1} a_{i, k_i} }\right)$

Now we need to show that the result is true for the product $\displaystyle \prod_{i \mathop = 1}^n p_i$.

Induction Step

This is our induction step:

Let $b_k$ be the coefficient of $X^k$ in $\displaystyle \prod_{i \mathop = 1}^n p_i$. Then:

\(\displaystyle b_k\) \(=\) \(\displaystyle \sum_{d + k_n \mathop = k} c_d a_{n, k_n}\) $\quad$ By the definition of polynomial multiplication $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{d + k_n \mathop = k}\ \sum_{k_1 + \cdots + k_{n-1} \mathop = d} \left({\prod_{i \mathop = 1}^{n-1} a_{i, k_i} }\right) a_{n, k_n}\) $\quad$ By the induction hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{d + k_n \mathop = k}\ \sum_{k_1 + \cdots + k_{n-1} \mathop = d} \left({\prod_{i \mathop = 1}^n a_{i, k_i} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{\substack{k_1 + \cdots + k_{n-1} \mathop = d \\ d + k_n \mathop = k} } \left({\prod_{i \mathop = 1}^n a_{i, k_i} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k_1 + \cdots + k_n = k} \left({\prod_{i \mathop = 1}^n a_{i, k_i} }\right)\) $\quad$ $\quad$

The result follows by induction.