## 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-k$th coefficient of $\prod (z-x_i)$ is the sum of all possible products of the variables $x_i$, chosen $k$ at a time.