# Polynomial for product over a set

Conjecture: If $$A$$ is a nonempty, finite set with size $$|A|=n$$, and $$P_A(x)=\prod_{a\in A}(x-a),$$ then $$P_A(x)$$ can be expanded as $$P_A(x)=\sum_{k=0}^{n}(-1)^{n-k}x^k\sum_{{U\subseteq A}\atop{|U|=n-k}}\prod_{u\in U}u.\tag{1}$$

I have conjectured this based on algebraic evidence. That is, I expanded out the cases $$n=1,...,4$$ both manually and through $$(1)$$, and in each case the conjecture held. The problem is, I'm having difficulty proving this result. I'm fairly certain that a proof would involve induction, but I'm not very good at that, and have so far failed.

I was initially interested in this formula because I recognized that $$(1)$$ would imply that $$k\ne0,n\iff \sum_{{U\subseteq S_n}\atop{|U|=k}}\prod_{u\in U}u=0\tag{2}$$ for $$S_n=\left\{\exp\frac{2\pi ik}{n}:k=0,1,...,n-1\right\}.$$ It may seem un-intuitive at first, but $$(2)$$ is true because $$P_{S_n}(x)=x^n-1,$$ (as $$S_n$$ is the set of roots of $$x^n-1$$) so each term of the expansion must vanish except for the cases $$k=0,n$$.

After seeing this, I was naturally curious about a proof of $$(1)$$. Could I have some help or hints? Thanks.

• The relation between product of linear factors and the polynomial written as a sum of powers goes by the name of Vieta's formulas – Winther Jun 24 at 0:09