Find the coefficients of a given polynomial

Let F be a field and let z, x_i be indeterminates. Find closed form expressions for the coefficients of the powers of z in s = \prod_{i=1}^n (z-x_i) \in F[z,x_1,\ldots,x_n].


Let n \in \mathbb{N}. We will let A^n_k denote the set of all k-element subsets of [1,n] \subseteq \mathbb{N}. We claim that

\displaystyle\prod_{i=1}^n (z-x_i) = \displaystyle\sum_{k=0}^n (-1)^{n-k} \left[ \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T} x_t \right] z^k.

We will prove this by induction on n. The cases n = 0 and n = 1 are trivial. Suppose now that the equation holds for some n, and note the following.

\displaystyle\prod_{i=1}^{n+1} (z-x_i)  =  \left[ \displaystyle\prod_{i=1}^n (z-x_i) \right] (z-x_{n+1})
 =  \left( \displaystyle\sum_{k=0}^n (-1)^{n-k} \left[ \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T} x_t \right] z^k \right) (z - x_{n+1})
 =  \left( \displaystyle\sum_{k=0}^n (-1)^{n-k} \left[ \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T} x_t \right] z^{k+1} \right) + \left( \displaystyle\sum_{k=0}^n (-1)^{n+1-k} \left[ x_{n+1} \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T} x_t \right] z^k \right)
 =  \left( \displaystyle\sum_{k=1}^{n+1} (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n}_{n+1-k}} \displaystyle\prod_{t \in T} x_t \right] z^{k} \right) + \left( \displaystyle\sum_{k=0}^n (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T \cup \{x_{n+1}\}} x_t \right] z^k \right)
 =  (-1)^0 \left[ \displaystyle\sum_{T \in A^n_0} \displaystyle\prod_{t \in T} x_t \right] z^{n+1} + \left( \displaystyle\sum_{k=1}^{n} (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n}_{n+1-k}} \displaystyle\prod_{t \in T} x_t \right] z^{k} \right) + \left( \displaystyle\sum_{k=1}^n (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T \cup \{x_{n+1}\}} x_t \right] z^k \right) + (-1)^{n+1} \left[ \displaystyle\sum_{T \in A^n_n} \displaystyle\prod_{t \in T \cup \{x_{n+1}\}} x_t \right] z^0
 =  (-1)^0 \left[ \displaystyle\sum_{T \in A^n_0} \displaystyle\prod_{t \in T} x_t \right] z^{n+1} + \left( \displaystyle\sum_{k=1}^{n} (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n}_{n+1-k}} \displaystyle\prod_{t \in T} x_t + \displaystyle\sum_{T \in A^{n}_{n-k}} \displaystyle\prod_{t \in T \cup \{x_{n+1}\}} x_t \right] z^{k} \right) + (-1)^{n+1} \left[ \displaystyle\sum_{T \in A^n_n} \displaystyle\prod_{t \in T \cup \{x_{n+1}\}} x_t \right] z^0

We claim that A^n_{t+1} \cup \{ T \cup \{n+1\} \ |\ T \in A^n_{t} \} = A^{n+1}_{t+1}. Indeed, the (\subseteq) direction is clear. Conversely, If T \subseteq [1,n+1] is an t+1-element subset, then either n+1 \notin T, so that T \subseteq [1,n] and thus T \in A^n_{t+1}, or n+1 \in T, in which case the remaining elements form a t-element subset of [1,n]. Moreover, note that A^n_0 = \{\emptyset\}. In particular, A^n_0 = A^m_0 for all n and m. Finally, If T \in A^n_n, then in fact T = [1,n]. In this case T \cup \{n+1\} = [1,n+1], so that T \cup \{n+1\} \in A^{n+1}_{n+1}. With these facts in mind, we have the following simplification.

\displaystyle\prod_{i=1}^{n+1} (z-x_i)  =  (-1)^0 \left[ \displaystyle\sum_{T \in A^{n+1}_0} \displaystyle\prod_{t \in T} x_t \right] z^{n+1} + \left( \displaystyle\sum_{k=1}^{n} (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n+1}_{n+1-k}} \displaystyle\prod_{t \in T} x_t \right] z^{k} \right) + (-1)^{n+1} \left[ \displaystyle\sum_{T \in A^{n+1}_{n+1}} \displaystyle\prod_{t \in T} x_t \right] z^0
 =  \displaystyle\sum_{k=0}^{n+1} (-1)^{n+1-k} \left[ \displaystyle\sum_{T \in A^{n+1}_{n+1-k}} \displaystyle\prod_{t \in T} x_t \right] z^k

As desired.

In words, the n-kth coefficient of \prod (z-x_i) is the sum of all possible products of the variables x_i, chosen k at a time.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: